The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Ciel the Commander

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNow 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!".

Input

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.

Output

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!".

Examples

Input

4

1 2

1 3

1 4

Output

A B B B

Input

10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

Output

D C B A D C B D C D

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/28/2023 02:32:41 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|