E. Бертауны замууд

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

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

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

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

Бертаунд $n$ тооны уулзварууд, $m$ тооны хоёр чиглэлтэй зам байна. Бид нэг уулзвараас нөгөө рүү тавигдсан замуудаар явж хүрч болно гэдгийг мэднэ.
Сүүлийн жилүүдэд машины тоо өдрөөс өдөрт өсөн нэмэгдэж буй нь замын түгжрэл үүсэх гол шалтгаан болж байна. Иймээс замын түгжрэлийг бууруулахын тулд засгийн газар бүх замуудыг нэг чиглэлтэй болгохоор шийдвэрлэв.

Та нэг уулзвараас дурын нэг уулзвар рүү хүрэх боломжийг хэвээр үлдээж бүх замуудыг нэг чиглэлтэй болгох боломж байгаа эсэхийг тодорхойлно уу. Хэрэв боломжтой бол замуудын байрлалыг тодорхойлох боломжит аргуудаас нэгийг олно уу.

Оролт

Эхний мөр нь $n$ болон $m$ ($2 ≤ n ≤ 10^{5}, n - 1 ≤ m ≤ 3*10^{5}$) гэсэн хоорондоо зайгаар тусгаарлагдсан бүхэ тоонууд агуулах ба эдгээр нь тосгонд буй нийт уулзварууд болон замуудын тоог тус тус харуулна. Зам тус бүрийг $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) гэсэн хоёр бүхэл тоо илэрхийлэх ба эдгээр нь тус замаар холбогдсон уулзаруудын тоог харуулна.

Оршин суугчид нэг уулзвараас дурын нэг уулзвар руу тавигдсан хоёр чиглэлтэй замаар явж хүрэх боломжтой. Зам тус бүр нь өөр өөр уулзваруудыг холбох ба хоёр уулзварын хооронд нэгээс илүү зам байхгүй.

Гаралт

Хэрэв энэ бодлогод зөв хариу байхгүй бол 0 гэж хэвлэ. Үгүй бол тус бүр нь зам бүрийн чиглэлийг харуулсан $p_{i}$ болон $q_{i}$ гэсэн бүхэл тоо агуулсан $m$ мөрүүдийг хэвлэнэ үү. Энэ ч $p_{i}$ урсгалаас $q_{i}$ урсгал руу нэг чиглэлтэй замаар явж хүрэх замын урсгалыг харуулна. Замуудыг ямар ч дарааллаар хэвлэж болно. Хэрэв хэд хэдэн зөв хариу байвал нэгийг нь хэвлэнэ үү.

Орчуулсан: Энхгэрэл

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

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