C. Граф хуваах

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

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

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

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

Бяцхан Крис граф хуваалтын тэмцээнд оролцож байна. Тэр мэргэжлийн. Түүний чадварыг бүрэн шалгах цаг ирлээ.

Крисд $m$ ирмэг $n$ оройтой (1-c $n$ хүртэл дугаарлагдсан) чиглэлгүй холбогдсон энгийн граф өгөгдсөн. Үүнийг 2 урттай ялгаатай ирмэгтэй замуудад хуваах нь гол асуудал юм. Өөрөөр хэлбэл Крис хос ирмэг бүр хөрш байх мөн ирмэг бүр нэг хос ирмэгт агуулагдсан байхаар графын бүх ирмэгүүдийг хос ирмэгүүдэд хуваах ёстой.

Жишээлбэл зурагт Крис графыг хувааж болох замыг харуулсан байна. Эхний жишээнд энэ графын тодорхойлолт агуулагдсан.

Танд Кристэй хамт оролцох боломж байна. Өгөгдсөн графыг хуваах замыг ол эсвэл боломжгүй эсэхийг тодорхойл.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 10^{5}$) байх ба графын оройнууд болон ирмэгүүдийн тоо юм. Дараагийн $m$ мөрөнд графын ирмэгүүдийн тодорхойлолт байна. $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $a_{i} ≠ b_{i}$) байх ба $i$-р ирмэгээр холбогдсон оройнуудын дугаар юм. Өгөгдсөн граф энгийн (өөртэйгээ холбогдоогүй ба давхар ирмэггүй) ба холбогдсон байна.

Тэмдэглэл: оролт ба гаралтын хэмжээ маш их байж болох ба таны програмчлалын хэлэн дахь удаан гаралтын аргуудыг битгий ашиглаарай. Жишээлбэл C++ хэлэнд оролт гаралтын (cin, cout) урсгалуудыг битгий ашиглаарай.

Гаралт

Хэрвээ өгөгдсөн графыг 2 урттай ялгаатай ирмэгтэй замуудад хувааж болохоор бол мөр хэвлэ. $i$-р мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоон утга $x_{i}$, $y_{i}$ ба $z_{i}$ байх ба $i$-р замын тайлбар юм. Граф уг замыг агуулж байх ёстой буюу граф $(x_{i}, y_{i})$ ба $(y_{i}, z_{i})$ ирмэгүүдийг агуулна гэсэн үг. Ирмэг бүр зөвхөн нэг ширхэг 2 урттай замд л хамаарагдах ёстой. Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

Өгөгдсөн графыг хуваах боломжгүй бол "No solution"-г (хашилтгүйгээр) хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
8 12
1 2
2 3
3 4
4 1
1 3
2 4
3 5
3 6
5 6
6 7
6 8
7 8
Гаралт
1 2 4
1 3 2
1 4 3
5 3 6
5 6 8
6 7 8
Оролт
3 3
1 2
2 3
3 1
Гаралт
No solution
Оролт
3 2
1 2
2 3
Гаралт
1 2 3
Сэтгэгдлүүдийг ачааллаж байна...