H. Замын асуудал

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

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

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

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

Берландын нийслэл нь $n$ тооны замын уулзвартай ба эдгээр нь хоёр урсгалтай замаар хоёр хоёроороо холбогдсон байна. Харамсалтай нь сүүлийн үед замын түгжрэл маш хурдацтай өсөн нэмэгдсэн учир хот шинэ зам барихаар шийджээ. Зам тус бүр хоёр уулзвараар холбогдоно.

Хотын захиргаа хөгжингүй орнуудын хотуудад хоёр замын хооронд дор хаяж хоёр чиглэлээр явж болох ба чиглэлүүд нь аль нэг замтай давхцахгүй боловч нэг уулзвар дээр нийлдэг туршлага байдаг талаар мэдэгдсэн юм. Берландын засгийн газар ч мөн үүнийг хэрэгжүүлэхийн тулд хамгийн багадаа хэдэн зам нэмэх ёстой вэ? Шинэчлэлийн өмнө болон дараа тус хотод хоёр уулзвар тутмын хооронд нэгээс илүү зам байх ёсгүй.

Оролт

Эхний мөр нь $n$, $m$ ($2 ≤ n ≤ 900, 1 ≤ m ≤ 100000$) гэсэн хос бүхэл тоо агуулах ба $n$ нь уулзварын тоог, $m$ нь замын тоог илэрхийлнэ. Доорх $m$ мөр тус бүр нь $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) холбоотой уулзваруудын өгөгдсөн тоогоор ирлэрхийлэгдсэн замын тодорхойлолтыг агуулсан байна. Мөрүүд нь 1-ээс $n$ хүртэл эрэмбэлэгдсэн байна. Хотын аль нэг нэг урсгалтай замаар аль ч уулзварт хүрэх боломжтой.

Гаралт

Эхний мөрөнд нэмэгдэж хийгдсэн замын $t$ тоог гарга. $t$ дахь мөрүүдэд оролтын мэдээллийн форматаар нэмэгдсэн замын тодорхойлолтыг гарга. Та зам болон зам тус бүрээр холбогдсон уулзваруудыг ямар ч дарааллаар ашиглаж болно. Хэрэв хэд хэдэн зөв хариу гарвал аль нэгийг сонго.
Хэрэв уг нийслэлд ямар нэгэн шинэчлэл шаардлагагүй бол 0 гарга.

Хариу гарах боломжгүй бол -1 гарга.

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

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

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