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.

這個題，我真的不知道什么是點分治。

我們就題論題，這個題說要是點分治我不太懂，但是這個題我的思路很簡單。這個題題意是說給一棵樹，子節(jié)點的級別相同的時父節(jié)點的級別一定是高于他們的。開始是這么理解的，但是后來我發(fā)現(xiàn)不是這么回事，放兩張圖大家理解一下。就明白為什么每次都需要找重心了。

一開始我想的是這樣：

?

但是后來我發(fā)現(xiàn)如果是這種情況的話：

?

?

?

?只有這樣才能把節(jié)點使用的最少進而達到題目要求。

#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; }

?

總結(jié)

以上是生活随笔為你收集整理的Codeforce 322E Ciel the Commander （点分治）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。