Codeforce 322E Ciel the Commander （点分治）

E. Ciel the Commander

Now 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 ≤ 105) — 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.

这个题，我真的不知道什么是点分治。

我们就题论题，这个题说要是点分治我不太懂，但是这个题我的思路很简单。这个题题意是说给一棵树，子节点的级别相同的时父节点的级别一定是高于他们的。开始是这么理解的，但是后来我发现不是这么回事，放两张图大家理解一下。就明白为什么每次都需要找重心了。

一开始我想的是这样：

但是后来我发现如果是这种情况的话：

 只有这样才能把节点使用的最少进而达到题目要求。

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int  maxn=100005;
int vis[maxn],son[maxn],f[maxn],sum,root,ans[maxn];
vector<int> E[maxn];
void dfsroot(int x,int fa)
{
    son[x]=1;f[x]=0;
    for(int i=0;i<E[x].size();i++)
    {
        int v = E[x][i];
        if(v == fa || vis[v])continue;
        dfsroot(v,x);
        son[x]+=son[v];
        f[x]=max(f[x],son[v]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root])root=x;
}//找树的重心
void work(int x,int fa,int dep)
{
    ans[x]=dep;
    vis[x]=1;
    for(int i=0;i<E[x].size();i++)
    {
        int v = E[x][i];
        if(vis[v])continue;
        sum=son[v],root=0;
        dfsroot(v,x);
        work(root,x,dep+1);
    }
}//染色
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        E[x].push_back(y);
        E[y].push_back(x);
    }
    f[0]=sum=n;
    dfsroot(1,0);
    work(root,0,0);
    for(int i=1;i<=n;i++)
        printf("%c ",ans[i]+'A');
    printf("\n");
    return 0;
}