E. Удирдагч Сиел

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

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

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

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

Сиел үнэг нь Триландын (Tree land) удирдагч болов. Триланд нь $(n - 1)$ ширхэг чиглэлгүй замаар холбогдсон $n$ хоттой ба аль ч $2$ хотын хооронд ямар нэг маршрут заавал байдаг.

Сиел хот бүрт нэг офицер томилох шаардлагатай байгаа бөгөөд офицер бүр нь $A$-аас $Z$ хүртэл цолтой. Мэдээж нийт 26 цол байх ба $A$ нь хамгийн дээд, $Z$ нь хамгийн доод цол болно.

Ямар ч цолны офицерийн тоо хангалттай боловч заавал дагах ёстой нэгэн дүрэм бий. Хэрэв $x$ болон $y$ хоёр хот нь ижилхэн цолтой офицертой бол $x$ болон $y$ хотуудыг холбосон маршрут дээр заавал эдгээр офицероос өндөр цолтой офицертой $z$ хот байх ёстой юм. Энэ дүрэм нь ижил цолтой офицеруудын харилцаа өндөр цолтой офицероор хянагдаж байхын тулд зохиогдсон юм.

Сиелд боломжит төлөвлөгөө гаргахад туслана уу. Хэрэв боломжгүй бол "Impossible!" гэж хэвлээрэй.

Оролт

Эхний мөрөнд хотуудын тоо болох бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) өгөгдөнө.

Дараачийн $(n - 1)$ мөрөнд мөр бүрд $a$, $b$ ($1 ≤ a, b ≤ n, a ≠ b$) тоонууд өгөгдөнө. Бүх хотууд $1$-ээс $n$ хүртэл дугаарлагдсан гэж үзэх ба $a$ болон $b$-ээр эдгээр дугаартай хотуудын хооронд чиглэлгүй зам байгаа гэж үзнэ. Мөн өгөгдсөн граф нь мод байна.

Гаралт

Хэрэв боломжит төлөвлөгөө байгаа бол зайгаар тусгаарлагдсан $n$ ширхэг тэмдэгтийг хэвлэнэ. $i$-р тэмдэгт нь $i$-р хотын офицерийн цолыг илэрхийлнэ.

Эсрэг тохиолдолд "Impossible!" гэж хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
4
1 2
1 3
1 4
Гаралт
A B B B
Оролт
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Гаралт
D C B A D C B D C D

Тэмдэглэл

Эхний жишээнд аль ч хоёр $B$ цолтой офицеруудын хоорондох маршрут дээр $A$ цолтой офицер байх юм. Иймээс энэ нь боломжит төлөвлөгөө болж чадна.

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