E. Цагийн механизмтай бөмбөг

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

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

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

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

Миний нэр бол Жэймс биГриз, би бол бүхэл ертөнцийн хамгийн ухаантай дээрэмчин мөн үнэт эрдэнэсийн ангууч. Миний адал явдлуудын талаар бичсэн номнууд мөн миний үйлдлүүдийн талаарх дуунууд байдаг ч та нар намайг үнэхээр эвгүй мөчид барих боломжтой байсан.

Би камеруудаас нуугдах боломжтой байсан, бүх хамгаалагчдыг зальдаж хэд хэдэн урхийг давсан гэвч эцэст нь би эрдэнэсийн хайрцагт хүрч үүнийг онгойлгоход би санаандгүй цагийн механизмтай бөмбөгийг эхлүүлсэн! Аз болж би ийм төрлийн бөмбөгнүүдтэй өмнө нь таарч байсан ба би цагийн механизмыг тодорхой аргаар бөмбөгийн хавтан дээрх холбоосуудыг утсуудаар холбосноор зогсоож болдог гэдгийг мэднэ.

Би $n - 1$ утсаар холбогдсон $n$ холбоос харж байна. Холбоосууд $1$-c $n$ хүртэлх бүхэл тоогоор дугаарлагдсан. Бөмбөг дараах нөхцөлүүдээс хамгаалдаг хамгаалалтын механизмтай: хэрвээ хэлхээг үүсгэж байгаа $k ≥ 2$ байх $c_{1}, c_{2}, ..., c_{k}$ холбоосууд оршин байвал өөрөөр $c_{1}$ болон $c_{2}$, $c_{2}$ болон $c_{3}$, $...$, $c_{k}$ болон $c_{1}$-н хооронд ялгаатай $k$ утас оршин байвал тэгээд бөмбөг шууд дэлбэрэх ба миний түүх энд дуусна. Ихэнхдээ хэрвээ хоёр холбоос нэгээс их утсаар холбогдсон байвал тэд $2$ урттай хэлхээ бүрдүүлнэ. Мөн холбоосыг өөртэй нь холбох хориотой.

Нөгөө талаас хэрвээ би нэгээс их утас салгавал (өөрөөр тухайн мөчид системд $n - 2$-с ихгүй утас байх) бусад хамгаалалтын шалгалт амжилтгүй болж мөн л бөмбөг дэлбэрнэ. Ингээд миний хийж чадах ганц зүйл бол нэг утсыг салгаж ямар ч хэлхээ биш байх нь баталгаатай өөр газарт залгах.

Би цагийн механизмыг зогсоохын тулд утаснуудыг хэрхэн тавихаа мэднэ. Гэвч миний цаг дуусах гэж байна! Намайг амьд гарахад туслана уу: бөмбөгийг салгахын тулд нэг утсыг салгаж өөр газарт залгах үйлдлүүдийн дарааллыг ол.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 500 000$) байх ба холбоосуудын тоо.

Дараагийн $n - 1$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$ ба $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$, $x_{i} ≠ y_{i}$) байх ба $i$-р утсаар холбогдож байгаа холбоосуудыг заана.

Үлдсэн $n - 1$ мөрөнд хайж буй системийн тайлбар ижил форматтай байна.

Эхлэх ба дуусах системүүд зөв байна гэсэн үг (өөрөөр холбоосыг өөртэй нь холбосон утаснуудыг хэлхээнүүд агуулахгүй).

Гаралт

Эхний мөрөнд $k$ ($k ≥ 0$) байх ёстой ба бөмбөгийг салгахад шаардлагатай нэг утсыг салгаж залгах үйлдлүүдийн хамгийн бага тоо.

Дараагийн $k$ мөр бүрт дөрвөн бүхэл тоон утга $a_{i}$, $b_{i}$, $c_{i}$, $d_{i}$ гаргах ба $i$-р алхам дээр $a_{i}$ ба $b_{i}$ холбоосуудыг холбож байгаа утсыг салгаж үүнийгээ $c_{i}$ ба $d_{i}$ холбоосуудруу залгах шаардлагатайг илэрхийлнэ. Мэдээж $a_{i}$ ба $b_{i}$ холбоосуудыг холбож байгаа утас системд байсан байх ёстой.

Байгаа системийг хайж буй системрүү хувиргах зөв дараалал олдохгүй бол $-1$-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Жишээ тестүүдийн хувьд үйлдлүүдийг тодорхой болгох зураг:

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