现在福克斯·希尔成为了树地的指挥官。 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”的军官将位于他们之间的路径上。所以这是一个有效的解决方案。