← 返回题目列表

Codeforces · 321/C

C. 指挥官夏尔

中文机器翻译题面 查看原题

现在福克斯·希尔成为了树地的指挥官。 Tree Land,正如它的名字所说,有n个城市,由n-1条无向道路连接,并且对于任何两个城市来说,它们之间总是存在一条路径。

Fox Ciel需要为每个城市指派一名军官。每个军官都有一个军衔——从“A”到“Z”的字母。所以会有 26 个不同的等级,“A”是最上面的,所以“Z”是最下面的。

各级别军官数量足够。但有一个必须遵守的特殊规则:如果x和y是两个不同的城市,并且它们的军官具有相同的军衔,那么在x和y之间的简单路径上一定存在一个城市z,其军官的军衔更高。该规则保证相同级别军官之间的通信将受到更高级别军官的监控。

帮助夏尔制定一个有效的计划,如果不可能,则输出“不可能!”。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105) — Tree Land 中的城市数量。

以下 n - 1 行中的每一行都包含两个整数 a 和 b (1 ≤ a, b ≤ n, a ≠ b) — 它们意味着 a 和 b 之间将有一条无向道路。考虑所有城市都从 1 到 n 编号。

它保证给定的图将是一棵树。

输出

如果存在有效平面,则一行输出n个空格分隔的字符——第i个字符是编号为i的城市的军官军衔。

否则输出“不可能!”。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

A B B B

输入 #2

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出 #2

D C B A D C B D C D

注意

在第一个示例中,对于任何两名级别为“B”的军官,一名级别为“A”的军官将位于他们之间的路径上。所以这是一个有效的解决方案。