C. Тоон тойрог

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

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

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

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

Вася самбар дээр тойрог хэлбэрээр $1$-ээс $n$ хүртэл $n$ ширхэг ялгаатай тоонуудыг дараалал хамаарахгүйгээр бичжээ. Тэгээд дараа нь $(a, b)$ $(a ≠ b )$ хоёр тоонуудыг сонгож аваад эдгээр тоонуудыг холбосон нумууд зурж эхэлжээ.

Гэхдээ яг хоёр төрлийн нумыг зурж байсан бөгөөд нэг нь $a$ болон $b$ цэгүүд хоорондоо хөрш байвал, хоёр дахь нь $a$ болон $b$ цэгүүдийг дундаа нэг ширхэг дугаартай байвал хооронд нь холбосон нумууд зуржээ. Ингэсээр нийтдээ Вася $2 \cdot n$ ширхэг нум зурсан байв.

Жишээ нь: хэрвээ тойрог хэлбэрээр $1, 2, 3, 4, 5$ дараалалтайгаар $5$-н тоо бичигдсэн бол нумууд дараах дугааруудын хооронд зурагдах юм: $(1, 2)$, $(2, 3)$, $(3, 4)$, $(4, 5)$, $(5, 1)$, $(1, 3)$, $(2, 4)$, $(3, 5)$, $(4, 1)$, $(5, 2)$.

Үүнээс хойш хэсэг хугацаа өнгөрч самбар дээрх дугаарууд арилжээ. Гэхдээ Васяд $2 \cdot n$ ширхэг хос дугаар бичсэн тэмдэглэл нь үлдсэн байв. Эдгээр хосууд нь түүний самбар дээр зурж байсан нумуудын $2$ үзүүрын дугаарууд юм. Вася таныг тойрогт бичигдсэн дугааруудын дарааллыг сэргээж өгөхийг гуйжээ.

Оролт

Эхний мөрөнд самбар дээр бичигдсэн нийт дугаарын тоо хэмжээ болох $n$ ($5 ≤ n ≤ 10^{5}$) өгөгдөнө. Дараагийн $2 \cdot n$ ширхэг мөрөнд нумуудын $2$ үзүүр болох дугаарууд $a_{i}$, $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n$; $a_{i} ≠ b_{i})$ өгөгдөнө.

Хоёр цэг нэгээс олон нумаар холбогдсон байх боломжгүй. Хос дугаарууд болон хос дугаарууд доторх дугааруудын дараалал санамсаргүйгээр байрласан байв.

Гаралт

Хэрвээ Вася нэг газар алдаа гаргасан бөгөөд $1$-ээс $n$ хүртэл дугааруудыг байрлуулах боломжгүй бол "-1" гэж хэвлэнэ үү. Харин олдож байвал $1$-ээс $n$ хүртэл дугаарын дарааллыг хэвлэнэ үү.

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

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

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

Оролт
5
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2
Гаралт
1 2 3 4 5 
Оролт
6
5 6
4 3
5 3
2 4
6 1
3 1
6 2
2 5
1 4
3 6
1 2
4 5
Гаралт
1 2 4 5 3 6 
Сэтгэгдлүүдийг ачааллаж байна...