D. Ноён Китаютагийн технологи

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

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

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

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

Шүсэкийн вант улс нь дэлхийд шинэ технологоор тэргүүлэгч улс юм. Уг вант улсад $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хот байдаг.

Ноён Китаютагийн эрдэм шинжилгээний ажил хоёр хотын хооронд шилжих хоолойг бүтээх боломжийг бүрдүүлжээ. Шилжих хоолой хоёр хотыг нэг чиглэлт байдлаар холбодог. Өөрөөр хэлбэл $x$ хотоос $y$ хот руу шилждэг хоолойгоор $y$ хотоос $x$ хот руу шилжиж болдоггүй байна. Хотуудын шилжих хоолой тун хөгжингүй тул хэрэв $x$ хотоос $y$ хот руу шилжих хоолой болон $y$ хотоос $z$ хотруу шилжих хоолой хоёулаа баригдсан бол $x$ хотоос $z$ хот руу хормын зуур шилжиж чаддаг байна.

Ноён Китаюта мөн улс төрийн бодлогод анхаардаг нэгэн аж. Тиймээс тэрээр $(a_{i}, b_{i})$ гэсэн $m$ $(1 ≤ i ≤ m)$ ширхэг хотуудын хоорондох холбоо онцолж үзжээ. Ийнхүү онцолсон $(a_{i}, b_{i})$ хос хот бүрийн хувьд $a_{i}$ хотоос $b_{i}$ хот руу шууд буюу дамжих замаар шилжин очих боломжтой байхаар шилжих хоолойнуудыг барихаар төлөвлөжээ.(Гэхдээ $b_{i}$ хотоос $a_{i}$ очиж чаддаг байх шаардлагагүй). Одоогоор ямар ч шилжих хоолой баригдаагүй байгаа ба хотууд хооронд ямар нэгэн зам байхгүй. Хамгийн багадаа хэдэн шилжих хоолой барих шаардлагатай вэ?

Оролт

Эхний мөрөнд Шүсэкийн вант улс дахь хотын тоо ба чухалчилсан хос хотуудын тоог илэрхийлэх $n$ ба $m$ ($2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5}$) тоонууд зайгаар тусгаарлагдан байрлана.

Дараагийн $m$ мөрөнд онцолсон хос хотуудыг дүрслэнэ. $i$ ($1 ≤ i ≤ m$) дэх мөрөнд нь $a_{i}$ хотоос $b_{i}$ хот руу шилжих хоолойгоор дамжин шилжиж чаддаг байх ёстойг илэрхийлэх $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) тоонууд зайгаар тусгаарлагдан байрлана. $b_{i}$ хотоос $a_{i}$ хотруу очиж чаддаг байх албагүй. Бүх $(a_{i}, b_{i})$ хосууд ялгаатай байх болно.

Гаралт

Ноён Китаютагийн зорилгыг биелүүлэхэд шаардагдах боломжит хамгийн бага шилжих хоолойн тоог хэвлэ.

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

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

Оролт
4 5
1 2
1 3
1 4
2 3
2 4
Гаралт
3
Оролт
4 6
1 2
1 4
2 3
2 4
3 2
3 4
Гаралт
4

Тэмдэглэл

Эхний жишээнд шилжих хоолойг барих хамгийн зөв хувилбарыг зурагт үзүүлэв:

Хоёр дахь жишээний боломжит нэгэн хувилбарийг доор үзүүлэв:

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