Построение декомпозиции

Простая

Ограничение по времени выполнения 2 секунды

Ограничение по использованию памяти 488,385 мегабайта

Постройте центроидную декомпозицию.

Вершина первого уровня должна иметь символ $« A »$ , второго уровня $« B »$ , и так далее...

Формат входных данных

Первая строка содержит одно целое число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ — количество вершин.

Каждая из следующих $n - 1$ строк содержит по два целых числа $v_{i}$ и $u_{i}$ $(1 \leq v_{i}, u_{i} \leq n)$ , что означает, что между вершинами $u_{i}$ и $v_{i}$ есть ребро.

Формат выходных данных

Выведите строку, состоящую из n символов. Если существует несколько возможных ответов, вы можете вывести любой из них.

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Отправки 7

Коэффициент принятия 57 %