Centroid Decompositon

//source : http://codeforces.com/contest/321/submission/23347823
// theory : https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

#include<bits/stdc++.h>
using namespace std;

#define si(n) scanf("%d",&n)
#define MAX 100005

vector<int>gr[MAX];
int n,tot_node;
int sz[MAX],ans[MAX];

void go(int now,int pr)
{
    tot_node++;
    sz[now]=1;
    for(int i=0;i<gr[now].size();i++){
        int to=gr[now][i];
        if(to==pr || ans[to]!=-1)continue;
        go(to,now);
        sz[now]+=sz[to];
    }
}

int go2(int now,int pr)
{
    for(int i=0;i<gr[now].size();i++){
        int to=gr[now][i];
        if(to == pr || ans[to] !=-1)continue;
        if(sz[to]>tot_node/2)return go2(to,now);
    }
    return now;
}

void decompose(int now,int par,int level)
{
    tot_node=0;
    go(now,par);
    int centroid=go2(now,par);
    //cout<<centroid<<endl;
    ans[centroid]=level;


    for(int i=0;i<gr[centroid].size();i++){
        int to=gr[centroid][i];
        if(ans[to]!=-1)continue;
        decompose(to,now,level+1);
    }
}


int main()
{
    //freopen("input.txt","r",stdin);
    int i,j;
    si(n);
    for(i=1;i<n;i++){
        int u,v;
        si(u);si(v);
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    memset(ans,-1,sizeof(ans));
    decompose(1,-1,0);
    for(i=1;i<=n;i++){
        //cout<<i<<' '<<ans[i]<<endl;
        printf("%c ",ans[i]+'A');
    }

    return 0;
}