A. Tree Labeling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree$$$^{[6]}$$$ of $$$n$$$ vertices, find the lexicographically$$$^{[2]}$$$ smallest string $$$s$$$ that satisfies the following:

  • String $$$s$$$ only consists of letters 'a', 'b', and 'c'.
  • For every edge $$$(u,v)$$$ of the tree, $$$s_u \neq s_v$$$.
Input

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

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — denoting the indices of the vertices connected by an edge.

It is guaranteed that the given edges form a tree.

Output

Output a single line, containing a string of length $$$n$$$ — the lexicographically smallest achievable string.

Examples
Input
3
1 2
1 3
Output
abb
Input
4
1 3
3 4
4 2
Output
aabc