Ciekl commander

Fox Ciel becomes the commander of Tree Land. In Tree Land, as the name suggests, there are $n$ 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, represented by a letter from 'A' to 'Z'. Thus, there are $26$ 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 $x$ and $y$ are two different cities and their officers have the same rank, then on the simple path between $x$ and $y$, there must be a city $z$ 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!".

Input

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 $a$ and $b(1\le a,b\le n,a\ne b)$, indicating that there is a road between cities $a$ and $b$. Assume that the cities are numbered from $1$ to $n$ in some manner.

It is guaranteed that the given graph will be a tree.

Output

If a suitable plan exists, print $n$ characters separated by spaces: the $i$-th character represents the rank of the officer in city $i$.

Otherwise, print "Impossible!".

Examples