CodeForces-321C: Ciel the Commander（点分治）

树分治

Description

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

Example

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.

题意：给出一棵树，给每一个点填上一个字母（A到Z，A最大）。要求每两个等级相同的点之间一定存在另一个点的等级更高。

分析：每次找出树的重心，从A到Z赋值，找出赋值之后将它删去，接着找它剩下的子树的各个重心。A到Z一共26个字母，但是$2^{17}$已经大于了100000，这就说明我们一定能用字母表示所有点的等级，而不会输出Impossible。（SPJ）

• 代码：

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
vector<int>v[100005];
int ans[100005],vis[100005];
int sz[100005];
int rt;
void getsz(int u,int fa) //得到size，即包含该节点在内以及它下方的节点个数
{
    sz[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        int next=v[u][i];
        if(next==fa||vis[next]) continue;
        getsz(next,u);
        sz[u]+=sz[next];
    }
}
void getrt(int u,int fa,int totsz)
{
    int upsz=totsz-sz[u];//u节点上方的大小
    int dnsz=-1;//下方的大小
    if(upsz>totsz/2)    return;
    for(int i=0;i<v[u].size();i++)
    {
        int next=v[u][i];
        if(next==fa||vis[next]) continue;
        dnsz=max(dnsz,sz[next]);
        getrt(next,u,totsz);
    }
    if(max(upsz,dnsz)<=totsz/2)
        rt=u;
}
void getans(int id,int dep)
{
    getsz(id,0);
    getrt(id,0,sz[id]);//以当前的节点id为起点，父节点为0
    int rtt=rt;
    vis[rtt]=1;
    ans[rtt]=dep+1;
    for(int i=0;i<v[rtt].size();i++)
    {
        int next=v[rtt][i];
        if(vis[next])   continue;
        getans(next,dep+1);
    }
}
int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        getans(1,0);
        for(int i=1;i<=n;i++)
            printf("%c ",ans[i]+'A');
        printf("\n");
        for(int i=0;i<=n;i++)
            v[i].clear();
    }
    return 0;
}