Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.

The park consists of n squares connected with (n?-?1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More PRecisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.

Andryusha wants to use as little different colors as possible. Help him to choose the colors!

The first line contains single integer n (3?≤?n?≤?2·105) — the number of squares in the park.

Each of the next (n?-?1) lines contains two integers x and y (1?≤?x,?y?≤?n) — the indices of two squares directly connected by a path.

It is guaranteed that any square is reachable from any other using the paths.

In the first line print single integer k — the minimum number of colors Andryusha has to use.

In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.

32 31 3output
31 3 2 input
52 35 34 31 3output
51 3 2 5 4 input
52 13 24 35 4output
31 2 3 1 2 Note
In the first sample the park consists of three squares: 1?→?3?→?2. Thus, the balloon colors have to be distinct.
Illustration for the first sample.
In the second example there are following triples of consequently connected squares:
1?→?3?→?21?→?3?→?41?→?3?→?52?→?3?→?42?→?3?→?54?→?3?→?5We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.Illustration for the second sample.
In the third example there are following triples:
1?→?2?→?32?→?3?→?43?→?4?→?5We can see that one or two colors is not enough, but there is an answer that uses three colors only.
Illustration for the third sample題意：給定N個節(jié)點，N-1個關(guān)系，并且任意節(jié)點所相連的節(jié)點的顏色都不相同，問最少多少種顏色可以實現(xiàn)，打印出每個節(jié)點的顏色思路：暴力求解，dfs（）來求解，一層一層的來求解AC代碼：
#include <iostream>#include <cstdio>#include <vector>using namespace std;const int MAX_N = 200005;vector<int> G[MAX_N];//用來表示圖int m,n,a,b;//n個節(jié)點int color[MAX_N];//每個節(jié)點的顏色int ans;void dfs(int now,int p){//now表示當(dāng)前節(jié)點，p表示和它相連的結(jié)點     int cur = 1;//用來記錄當(dāng)前的顏色     for(int i = 0;i < G[now].size();++i){        int v = G[now][i];        if(v == p){//說明當(dāng)前的這個結(jié)點所連接的這個結(jié)點已經(jīng)圖過色了            continue;        }        while(cur == color[p] || cur==color[now]){//求得可以涂的最大顏色；            cur++;        }        color[v] = cur++;        ans = max(ans,color[v]);        dfs(v,now);     }}int main() {    cin >> n;    ans = 0;    for (int i = 0; i < n-1; i++) {//        cin >> a >> b;        G[a].push_back(b);        G[b].push_back(a);    }    color[1] =1;    dfs(1,0);    printf("%d/n",ans);    for(int i = 1;i <= n;i++){        printf("%d ",color[i]);    }    return 0;}.真的是，自己對深搜的理解簡直差的要死，做起題目來感覺會寫，但寫的時候很容易錯，繼續(xù)加油吧，人一我十，總能趕上的。