E. Азтай улс

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

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

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

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

Петя азын тоонд дуртай. Хүн бүр эерэг утгатай тоо аравтын орон нь $4$ болон $7$ агуулаагүй бол азын тоо байна гэдгийг мэднэ. Жишээ нь: $47$, $744$, $4$ тоонууд нь азын тоонууд бол $5$, $17$, $467$ эдгээр нь азын тоо биш юм.

Нэгэн орой Петя унтаж байхдаа нэгэн арлын улсын ерөнхийлөгч болж байна гэж зүүдлэв. Тус улс нь өөр хоорондоо хоёр урсгалтай замаар холбогдсон арлуудаас бүрдэнэ. Зарим арлуудын хооронд зам байхгүй бол зарим арлууд хоорондоо замаар холбогдсон. Тиймээс энэ улс хэд хэдэн бүс нутагт хуваагджээ. Тодруулбал арал тус бүр яг нэг бүсэд харъялагдана. Нэг бүсэд орших хоёр арлын хооронд зам байна. Харин өөр бүсүүдэд хамаарах арлуудын хооронд зам байхгүй. Хэрэв тухайн бүсэд байх арлуудын тоо азын тоо гарвал тэр бүс нь азтай бүс юм.

Жинхэнэ ерөнхийлөгчийн хувьд Петя эхлээд ерөнхийлөгчийн ордон барихыг хүсэв. Азтай тоонд дуртай учир тэрээр өөрийн ордноо аль нэг азтай бүсэд барихыг хүсэв. Гэвч тус улсад эхэндээ тийм бүс байхгүй байх магадлалтай. Энэ тохиолдолд Петя өөр хоёр бүсүүдийн хооронд зам барьж холбож болох юм. Азтай бүс бий болгохын тулд хамгийн багадаа хэдэн зам барих шардлагатайг олно уу.

Оролт

Эхний мөр нь $n$ болон $m$ ($1 ≤ n, m ≤ 10^{5}$) гэсэн хоёр бүхэл тоо агуулна. Эдгээр нь нийт арлуудын тоо, замын тоог тус тус илэрхийлнэ. Дараагийн $m$ мөрүүд нь замуудын тодорхойлолтыг агуулна. Зам тус бүр нь холбож буй хотынхоо тоогоор илэрхийлэнднэ: энэ нь $u$ болон $v$ ($1 ≤ u, v ≤ n$) гэсэн хоёр хоёр бүхэл тоогоор илэрхийлэгднэ. Зарим зам нь өөрөө аралтай холбогдно. Хоёр арлын хооронд нэгээс илүү зам байж болно. Мөр тус бүрт байгаа тоо хоорондоо нэг зайгаар тусгаарлагдна.

Гаралт

Хэрэв энэ бодлогод зөв хариу байхгүй бол -1 гаргана уу. Эсвэл азтай бүсийг бий болгох замын хамгийн бага тоо $r$-г тоог гарга.

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

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

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