Building a Decomposition

Construct the centroid decomposition of a tree.

Assign the symbol $«A»$ to the vertex at the first level, $«B»$ to the vertex at the second level, and continue similarly for subsequent levels.

Input Format

The first line contains a single integer $n$ $(1\le n\le 2\cdot 10^5)$, representing the number of vertices in the tree.

Each of the following $n-1$ lines contains two integers $v_i$ and $u_i$ $(1\le v_i,u_i\le n)$, indicating an edge between vertices $v_i$ and $u_i$.

Output Format

Output a string of n characters. If there are multiple valid outputs, you may provide any one of them.

Examples