B. Зам тавих

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

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

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

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

Нэгэн улс n ширхэг хоттой. Анх тэнд ганц ч зам байгаагүй. Нэгэн өдөр хаан хотуудыг хоёр хоёроор нь холбосон хэсэг зам тавихаар шийджээ. Зам нь 2 чиглэлд аялах боломжтой. Тэрбээр замуудаа тавихдаа ямар ч хоёр хотын хооронд хамгийн ихдээ 2 зам ашиглаад хүрэх боломжтой байхыг хүсч байгаа. Танд мөн m ширхэг хос хотууд өгөгдсөн ба та эдгээр хосуудын хооронд зам тавьж чадахгүй.

Таны даалгавар нь дээрх нөхцлийг хангасан байхаар хамгийн цөөн зам тавих юм. Үргэлж бодлогын нөхцлийг хангах зам тавих боломжтой байна.

Оролт

Эхний мөрөнд n ба m тоонууд өгөгдөнө .

Дараагийн m мөр тус бүр ai болон bi тоонууд өгөгдөнө (1 ≤ ai, bi ≤ n, ai ≠ bi). Эдгээр тоонууд нь зам тавигдах боломжгүй хотуудын хосуудыг илэрхийлнэ. Хотууд нь 1-ээс n хүртэл дугаарлагдсан.

Оролтонд ямар ч хос хамгийн ихдээ ганц л байна.

Гаралт

Эхний мөрөнд хамгийн цөөн замын тоог илэрхийлэх s тоо. Дараагийн s мөрүүдэд аль хотуудын хооронд зам тавих хэрэгтэйг заасан ai ба bi (1 ≤ ai, bi ≤ n, ai ≠ bi) тоонуудыг хэвлэ.

Олон хариутай тохиолдолд алийг нь ч хэвлэж болно.

Орчуулсан: Хонгор

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

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

Тэмдэглэл

This is one possible solution of the example:

These are examples of wrong solutions:

The above solution is wrong because it doesn't use the minimum number of edges ($4$ vs $3$). In addition, it also tries to construct a road between cities $1$ and $3$, while the input specifies that it is not allowed to construct a road between the pair. The above solution is wrong because you need to traverse at least $3$ roads to go from city $1$ to city $3$, whereas in your country it must be possible to go from any city to another by traversing at most $2$ roads. Finally, the above solution is wrong because it must be possible to go from any city to another, whereas it is not possible in this country to go from city $1$ to $3$, $2$ to $3$, and $4$ to $3$.

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