Ciel the Commander

题意翻译

##题面 现在Fox Ciel成为了Tree Land的指挥官。 Tree Land，正如它的名字所说，有n个城市由n-1条无向道路连接，并且其中任意两个城市之间总是存在一条路径。 Fox Ciel需要在每个城市分配一个官员。每个官员都有一个等级---一个’A’到’Z’之间的字母。所以会有26个不同的等级，’A’是最高的，’Z’是最低的。 每个等级都有足够的官员。但是必须遵守一个特殊的规则： ——如果x和y是两个不同的城市并且他们的官员拥有相同的等级，那么x和y之间的简单路径中一定存在一个城市z有更高等级的官员。 这个规则可以保证两个同等级官员之间的通信会由较高等级的官员监控。 帮助Ciel制定一个有效的计划，如果这是不可能的，输出"Impossible!"。 ##输入 第一行包含一个整数n (2 ≤ n ≤ 10^5)---Tree Land的城市数。 接下来的n-1行包含两个整数a和b (1 ≤ a, b ≤ n, a ≠ b)---表示a和b之间有一条无向的道路。城市的编号从1到n。 保证题目给出的图是一棵树。 ##输出 如果存在一个有效的计划，在一行里输出由空格分隔的n个字符，第i个字符表示第i个城市里官员的等级。 否则输出"Impossible!"。

题目描述

Now Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has $ n $ cities connected by $ n-1 $ undirected roads, and for any two cities there always exists a path between them. Fox Ciel needs to assign an officer to each city. Each officer has a rank — a letter from 'A' to 'Z'. So there will be 26 different ranks, and 'A' is the topmost, so 'Z' is the bottommost. There are enough officers of each rank. But there is a special rule must obey: if $ x $ and $ y $ are two distinct cities and their officers have the same rank, then on the simple path between $ x $ and $ y $ there must be a city $ z $ that has an officer with higher rank. The rule guarantee that a communications between same rank officers will be monitored by higher rank officer. Help Ciel to make a valid plan, and if it's impossible, output "Impossible!".

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 2<=n<=10^{5} $ ) — the number of cities in Tree Land. Each of the following $ n-1 $ lines contains two integers $ a $ and $ b $ ( $ 1<=a,b<=n,a≠b $ ) — they mean that there will be an undirected road between $ a $ and $ b $ . Consider all the cities are numbered from 1 to $ n $ . It guaranteed that the given graph will be a tree.

输出格式

If there is a valid plane, output $ n $ space-separated characters in a line — $ i $ -th character is the rank of officer in the city with number $ i $ . Otherwise output "Impossible!".

输入输出样例

输入样例 #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

说明

In the first example, for any two officers of rank 'B', an officer with rank 'A' will be on the path between them. So it is a valid solution.