322E - Ciel the Commander - CodeForces Solution

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;

#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int> 
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
#define PI acos((ld)-1)

typedef complex<ld> base;
typedef vector<base> vb;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MN=1e5+5;

int n,m;
int a,b;
vi son[MN];
int sub[MN];
char ans[MN];
bool check[MN];

int dfs(int u,int par){
    sub[u]=1;
    for(int v:son[u]){
        if(check[v]) continue;
        if(v==par) continue;
        sub[u]+=dfs(v,u); 
    }
    return sub[u];
}

int centroid(int u,int par,int sz){
    for(int v:son[u]){
        if(v==par) continue;
        if(check[v]) continue;
        if((sub[v]<<1)>sz) return centroid(v,u,sz);
    }
    return u;
}

bool solve(int u,int par,int idx){
    // cout<<"Case "<<u<<": ";
    if(idx>=26) return false;
    
    int sz=dfs(u,par);

    u=centroid(u,par,sz);
    check[u]=true;
    ans[u]='A'+(idx++);
    // cout<<u<<' '<<ans[u]<<'\n';

    // cout<<"Case "<<u<<": ";
    for(int v:son[u]){
        // if(v==par) continue;
        // cout<<v<<' ';
        // adj[v].erase(u);
        if(check[v]) continue;
        if(!solve(v,u,idx)) return false;
    }
    // cout<<'\n';
    return true;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    /*
    freopen(taskname".inp","r",stdin);
    freopen(taskname".out","w",stdout);
    */

    // memset(ans,'Z',sizeof(ans));
    cin>>n; m=n-1;
    while(m--){
        check[m]=false;
        cin>>a>>b;
        son[a].eb(b); son[b].eb(a);
    }
    check[n-1]=check[n]=false;

    dfs(1,1);
    if(!solve(1,1,0)){
        cout<<"Impossible!";
        return 0;
    }

    for(int i=1;i<=n;++i){
        cout<<ans[i]<<' ';
    }
}