C. Зам ба төгөл

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

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

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

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

Васиа цэцэрлэгээр зугаалжээ. Цэцэрлэг 1-ээс $n$ дугаар бүхий төгөлтэй. Төглүүдийг холбосон $m$ зам байдаг ба 1-ээс $m$ дугаартай. $i$-дэх зам нь $x_{i}$ ба $y_{i}$ төглүүдийг холбосон. Холбогдсон төглүүд ижил байж болноm $(x_{i} = y_{i})$. Өөрөөр хэлбэл өөрөөс нь өөрлүү нь очсон зам байж болно. Мөн 2 төгөл үл огтлолцох хэд хэдэн замуудаар холбодсон байж болно.

Васиа 1 дэх төгөлд байгаа. Тэрээр зам бүрээр яг нэг нэг удаа явахыг хүсч байгаа бахамгийн сүүлд эргээд 1 дэх төгөлд ирэхийг хүсчээ. Харамсалтай нь тэр ингэх боломжтой эсэхийг мэдэхгүй байгаа. Түүнд боломжтой эсэхийг нь олоход туслана уу. Хэрэв боломжгүй бол боломжтой болгохын тулд хамгийн цөөндөө хэдэн зам нэмэх ёстойг олно уу.

Васиа замаас замруу шилжихдээ зөвхөн төгөлөөр дамжина. Замаар аль ч чиглэлийн дагуу явж болно. Хэрэв Васиа $a$ ба $b$ төглийг холбосон замаар $a$-аас гарсан бол $b$ төгөлд зам дуусна. .

Оролт

Эхний мөрөнд төгөлийн тоо ба замын тоог илэрхийлэх $n$ ба $m$ $(1 ≤ n ≤ 10^{6}; 0 ≤ m ≤ 10^{6})$ бүхэл тоонууд байрлана. Дараагийн $m$ мөрөнд замыг тодорхойлно. $i$-дэх мөрөнд $i$-дэх замаар холбогдсон хотууд болох $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n)$ байна.

Гаралт

Хэрэв Васиа нэмэлт замгүйгээр явж чадах бол "$0$" гэж хэвлэ, боломжгүй бол боломжтой болгоход шаардагдах хамгийн бага замын тоог хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
3 3
1 2
2 3
3 1
Гаралт
0
Оролт
2 5
1 1
1 2
1 2
2 2
1 2
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр зам нэмэх шаардлагагүй. 1, 2, 3 замыг дарааллан хэрэглэхэд болно.

Хоёрдахь жишээн дээр боломжтой болгохын тулд 1 болон 2 дугаар төгөлийг замаар холбоход хангалттай.

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