Ciel commander#11704
Fox Ciel becomes the commander of Tree Land. In Tree Land, as the name suggests, there are cities connected by n - 1 undirected roads, ensuring that there is a path between any two cities in Tree Land.
Fox Ciel needs to assign an officer to each city. Each officer has a rank — a letter from 'A' to 'Z'. Thus, there are different ranks, with 'A' being the highest and 'Z' being the lowest.
Ciel has a sufficient number of officers for each rank. However, a special condition must be met: if and are two different cities and their officers have the same rank, then on the simple path between and , there must be a city with an officer of a higher rank. This ensures that communication between officers of the same rank will always be overseen by an officer of a higher rank.
Help Ciel create a suitable plan for assigning officers to cities. If it is not possible, print "Impossible!".
The first line contains an integer n~(2 \le n \le 10^5) — the number of cities in Tree Land.
Each of the following n - 1 lines contains two integers and b~(1 \le a, b \le n, a \ne b) — indicating that there is a road between cities and . Assume that the cities are numbered from to in some manner.
It is guaranteed that the given graph will be a tree.
If a suitable plan exists, print characters separated by spaces: the -th character represents the rank of the officer in city .
Otherwise, print "Impossible!".
Example 1
Example 2