B. Домгийн аварга могой

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг удаа Петягийн төрсөн өдрөөр ээж нь түүнд "Графын онолын үлгэр домгууд" нэртэй ном бэлэглэжээ. Энэ номноос Петя домгийн аварга могой графын тухай олж мэджээ.

Доорх зурагт харуулсан шиг бүтэцтэй чиглэлт бус граф бол домгийн аварга могой юм. Тухайлбал $u$, $v$ хоёр орой хоорондоо ирмэгээр холбогдсон бөгөөд тэдгээр нь харгалзан могойн цээж болон ходоод юм. Цээжтэй $h$ оройнууд холбогддог ба эдгээрийг могойн толгойнууд гэдэг, харин ходоодтой $t$ оройнууд холбогддог ба эдгээрийг могойн сүүлнүүд гэнэ. Могой бол $h + t + 2$ оройноос бүрдсэн мод гэдгийг анхаараарай.

Мөн Петяд $n$ орой болон $m$ ирмэгээс бүрдсэн чиглэлт бус $G$ граф байдаг. Энэ графыг өнгөрсөн жилийн төрсөн өдрөөр нь түүний ээж Петяд бэлэглэсэн юм. $G$ графд өөрийгөө өөртэйгээ холбосон ямар ч гогцоо эсвэл хоёр оройг шууд холбосон олон ирмэг байдаггүй байна.

Одоо Петя $G$ графаас домгийн аварга могойг олохыг хүсэж байна.

Оролт

Эхний мөрөнд $n$, $m$, $h$, $t$ ($1 ≤ n, m ≤ 10^{5}$, $1 ≤ h, t ≤ 100$) дөрвөн бүхэл тоо байна. $n$ тоо нь $G$ графын оройнуудын тоо, $m$ тоо нь ирмэгүүдийн тоо, $h$, $t$ нь могойн толгой болон сүүлнүүдийн тоо юм.

Дараагийн $m$ мөрүүд нь $G$ графын ирмэгүүдийн тайлбарыг агуулна. $i$-р мөрөнд $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a ≠ b$) хоёр бүхэл тоо байх ба эдгээр оройнуудыг $i$-р ирмэгээр холбосон гэсэн утгатай.

$G$ графд өөрийгөө өөртэйгээ холбосон ямар ч гогцоо эсвэл олон ирмэг байдаггүй байна. Мөн $G$ графын ирмэгүүдийг $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан гэж үзнэ.

Гаралт

$G$ графаас домгийн аварга могой олдохгүй бол"NO" (хашилтгүйгээр) гэж хэвлэнэ.

Эсрэг тохиолдолд эхний мөрөнд "YES" (хашилтгүйгээр) гэж хэвлэнэ. Дараагийн мөрөнд $u$ ба $v$ оройнуудын дугаарыг хэвлэнэ. Гуравдугаар мөрөнд могойн толгойг төлөөлсөн оройнуудын дугаарууд болох $h$ тоонууд хэвлэнэ. Дөрөв дэх мөрөнд могойн сүүлийг төлөөлсөн оройнуудын дугаарууд болох $t$ тоонууд хэвлэнэ. Хэвлэсэн бүх тоонууд хоорондоо ялгаатай байна.

Хэрвээ хэд хэдэн хариулт байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
9 12 2 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5
8 7
9 1
Гаралт
YES
4 1
5 6 
9 3 2 
Оролт
7 10 3 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5
Гаралт
NO

Тэмдэглэл

Эхний жишээг доорх зурагт дүрсэлсэн байна:

Сэтгэгдлүүдийг ачааллаж байна...