C. Графын сэргээн босголт

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

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

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

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

Надад 1-с $n$ хүртэл дугаарлагдсан $n$ зангилаанаас бүрдсэн чиглэлгүй граф байна. Зангилаа бүр нь хамгийг ихдээ хоёр ирмэгтэй. Зангилаануудын хос бүрийг холбосон ирмэг хамгийн ихдээ нэг байна. Зангилааг өөртэй нь холбосон ирмэг байх ёсгүй.

Би ийм байдлаар шинэ граф үүсгэхийг хүсэж байна:

  • Шинэ граф нь хуучин графынхтай ижил тооны зангилаанууд болон ирмэгүүдтэй.
  • Эхний хэсгийн шинж чанарыг хэвээр хадгална.
  • $u$ ба $v$ зангилаа бүрийн хувьд хэрвээ хуучин графд тэднийг холбосон ирмэг байдаг байсан бол шинэ графд тэднийг холбосон ирмэг байхгүй байна.

Шинэ графыг байгуулахад надад туслаач, эсвэл энэ боломжгүй бол надад хэлээрэй.

Оролт

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

Гаралт

Хэрвээ энэ дурдсан шинж чанартай шинэ графыг байгуулах боломжгүй бол гаралтын нэг мөрөнд -1 гэж хэвлэнэ. Эсрэг тохиолдолд $m$ мөрүүд хэвлэнэ. Мөр бүр нь оролтонд ашиглагдсан хэлбэрийн ирмэгүүдийн тодорхойлолтыг агуулах ёстой.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхний жишээний хуучин граф:

Эхний жишээний боломжит шинэ граф:

Хоёрдугаар жишээнд бид шинэ графыг үүсгэж чадахгүй.

Гуравдугаар жишээний хуучин граф:

Гуравдугаар жишээний боломжит шинэ граф:

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