E. Мэдээллийн төв

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

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

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

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

Нэгэн том Програм хангамжын Компаний мэдээллийн төвийн төсөл нь $m$ ширхэг кабелиар холбогдсон $n$ ширхэг компьютерээс бүтдэг. Энгийнээр компьютер болгоныг хэд хэдэн кабель залгагдсан хайрцаг гэж үзэж болно. Кабель болгоноор 2 чиглэлийн аль нэг чиглэл уруу Маш Чухал Мэдээлэл дамжуулагддаг. Мэдээллийн төвийн төсөл хараахан хэрэгжээгүй байгаа болохоор кабель болгоноор аль чигт мэдээлэл явахыг хараахан зааж өгөөгүй байгаа. Кабелийг компьютер болгоныг хооронд нь холбогдож байхаар залгасан (энд хэд хэдэн комьпютерээр дамжин өнгөрч болно).

Мэдээллийн төвийн цэвэрлэгээний ажлыг хариуцаж авсан хүн нь Цэвэрлэгч Клаудиа Иванова. Тэрээр кабелиудыг нэгтгэн багц болгох дуртай. Зарим шалтгааны үүднээс, тэрээр кабелиудыг 2 багц болгон хуваах гэж байгаа бөгөөд хэрвээ энэ нь боломжгүй бол тэр уурлан компьютер уруу хувинтай ус барин дайрдаг.

Энд Маш Чухал Мэдээллийн тусгай чанараас болоод өөр чиглэлд мэдээлэл дамжуулах 2 кабелийг нэг багцад хуваарилах нь хориотой.

Мэдээллийн төвийн удирдлага нь Клаудиа Иванова кабелиудыг 2 багц болгон хуваах боломжтой байхаар мэдээллүүдийн чиглэлүүдийг шийдэхийг хүсч байгаа. Энэ нь боломжгүй байж болох учраас та аль болох бага тооны кабелийг нэмж болно. Үүний дараа та нэмсэн кабелиудаар аль чиглэлд мэдээлэл дамжихыг зааж өгнө. (Тиймээ, зарим тохиолдолд мэдээллийн төв нь цэвэрлэгчийн тав тухаас хамааран төлөвлөгөө гаргах шаардлагатай болдог...)

Оролт

Эхний мөрөнд компьютерийн тоо болон одоо байгаа кабелийн тоо болох 2 тоо $n$ ба $m$ ($1 ≤ n ≤ 100 000$, $1 ≤ m ≤ 200 000$) өгөгдөнө.

Дараагийн мөр болгон $i$ дэхь кабелийн холбогдсон компьютерүүдийн дугаарууд болох 2 тоонууд $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) өгөгдөнө. Мэдээллийн төвүүд маш ярвигтай байгуулалттай байдаг бөгөөд зарим хос компьютер нь нэгээс олон кабелиар хоорондоо холбогдсон байж болдог. Үүнээс гадна зарим кабелиуд нь компьютерийг өөртэй нь холбох ч тохиолдол байдаг.

Гаралт

Эхний мөрөнд нэг ширхэг тоо $p$ ($p ≥ m$) хэвлэнэ үү. Энэ нь эцэст байх боломжит хамгийн бага нийт кабелийн тоо.

Дараагийн $p$ ширхэг мөр болгонд хос тоонууд $c_{i}, d_{i}$ ($1 ≤ c_{i}, d_{i} ≤ n$)-ыг хэвлэнэ үү. Энэ нь кабель болгоны тайлбар. Энд кабелиар дамжих мэдээллийн чиглэлийг $c_{i}$ компьютерээс $d_{i}$ хүртэл гэж хэвлэсэнээр тайлбарлагдана.

Таны хэвлэсэн кабелиудад өгөгдөлд өгсөн кабелиуд байх ёстой бөгөөд гагцхүү чиглэлийг нь тодорхойлж өгөх үүднээс байрыг нь солиж болно. Энд $p$ нь $500 000$-г хэтрэхгүй байхаар хариулт олдоно.

Хэрвээ нэгээс олон хариулт байвал дурын нэгийг хэвлэнэ үү.

Орчуулсан: Энхлут

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

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

Тэмдэглэл

Эхний жишээний зураг. Багцлагдсан кабелиуд нь нэг цэгээс гарж байгаагаар дүрслэв.

2 дахь жишээний зураг. Нэмэгдсэн кабелиудыг тодоор зурав.

2 дахь жишээний бас нэгэн хариулт:

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