C. Командир Ciel
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лиса Ciel становится командиром Древоземелья. В Древоземелье, как это следует из названия, есть n городов, соединенных n - 1 ненаправленными дорогами, а между любыми двумя городами существует путь по дорогам Древоземелья.

Лиса Ciel должна назначить каждому городу офицера. У каждого офицера есть ранг — буква от 'A' до 'Z'. Таким образом, имеется 26 различных рангов, самый высокий — 'A', самый низкий — 'Z'.

У Ciel имеется достаточно офицеров каждого ранга. Но не все так просто, должно быть выполнено особое условие: если x, y — два различных города и у их офицеров одинаковые ранги, то на простом пути между x и y должен быть город z, имеющий офицера более высокого ранга. Таким образом, общение между офицерами одного ранга будет гарантированно проходить под присмотром офицера более высокого ранга.

Помогите Ciel составить подходящий план назначения офицеров городам. Если это невозможно, выведите «Impossible!».

Входные данные

В первой строке записано целое число n (2 ≤ n ≤ 105) — количество городов в Древоземелье.

В каждой из следующих n - 1 строк записано два целых числа a и b (1 ≤ a, b ≤ n, a ≠ b) — это значит, что существует дорога между городами a и b. Считайте, что города пронумерованы от 1 до n некоторым образом.

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

Выходные данные

Если подходящий план существует, выведите 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', офицер с рангом 'А' будет на пути между ними. То есть, такое решение подходит.