Командир Ciel#11704

Командир Ciel

1 секунда

128 мегабайтів

Складна

Лисиця Сіель стає командиром Древоземлі. У Древоземлі, як це випливає з назви, є $n$ міст, з'єднаних $n - 1$ n - 1 ненаправленими дорогами, а між будь-якими двома містами існує шлях по дорогах Древоземлі.

Лисиця Сіель повинна призначити кожному місту офіцера. У кожного офіцера є ранг — літера від 'A' до 'Z'. Таким чином, існує $26$ різних рангів, найвищий — 'A', найнижчий — 'Z'.

У Сіель є достатньо офіцерів кожного рангу. Але не все так просто, повинна бути виконана особлива умова: якщо $x$ , $y$ — два різних міста і у їхніх офіцерів однакові ранги, то на простому шляху між $x$ і $y$ повинно бути місто $z$ , яке має офіцера з вищим рангом. Таким чином, спілкування між офіцерами одного рангу буде гарантовано проходити під наглядом офіцера з вищим рангом.

Допоможіть Сіель скласти відповідний план призначення офіцерів містам. Якщо це неможливо, виведіть "Impossible!".

Вхідні дані

У першому рядку записано ціле число $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — кількість міст у Древоземлі.

У кожному з наступних $n - 1$ n - 1 рядків записано два цілих числа $a$ і $b (1 \leq a, b \leq n, a \neq = b)$ b~(1 \le a, b \le n, a \ne b) — це означає, що існує дорога між містами $a$ і $b$ . Вважайте, що міста пронумеровані від $1$ до $n$ певним чином.

Гарантується, що заданий граф буде деревом.

Вихідні дані

Якщо відповідний план існує, виведіть $n$ символів, розділених пробілами: $i$ -й символ позначає ранг офіцера в місті $i$ .

В іншому випадку, виведіть "Impossible!".

Приклади

Приклад 1

Приклад 2