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!

Input

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.

Output

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.

Examples

Input

3
2 3
1 3

Output

3
1 3 2

Input

5
2 3
5 3
4 3
1 3

Output

5
1 3 2 5 4

Input

5
2 1
3 2
4 3
5 4

Output

3
1 2 3 1 2

题意：给你一棵树，让你对其进行染色，使得任意相邻的三个节点颜色都不相同。

题目思路：

三个节点，所以我们保留上一个节点 ，假设 a->b->c

我们染c的时候，我们需要知道a和b分别是什么颜色，所以我们保留a与b的颜色。

然而会出现一个问题 a->b  b->c  b->d 这样的话，d与c也不能相同颜色，也就是说一个节点的孩子节点与这个节点都互不相同

第一步：我们存下来 a与b ，所以 下一个要访问的节点很容易确定颜色，从1开始只要不与a和b颜色相同即可。

第二步：b与d ，颜色不相同，我们只需要让c的颜色继续+1，只要这是的颜色不与 a和b 相同，所以 d的颜色也赋值了，并且dc绝对不相同因为，d=c+i  (i=1,2,3)。

一句话来说，我们对于每一个节点的下一层来言总让他从1开始判断(颜色最少),当不等于上一级与上一级颜色时，就让他赋予该颜色。然后继续增加，给该层的节点继续赋值。这样就保证了 既不与同层的相同，也不与祖先相同。

按这个思路实现的话，BFS应该会好点？

我使用的DFS：

#include <bits/stdc++.h>
/*#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>*/
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1000;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p;
int head[maxn];
struct node{
    int e,next;
}edge[maxn];
ll cnt=0;
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
    edge[cnt]=node{u,head[v]};
    head[v]=cnt++;
}
int vis[maxn],cot=0;//属于哪种颜色
int in[maxn];
void dfs(int u,int fa)
{
    int pos=1;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int e=edge[i].e;
        int f=0;
        if(!vis[e])
        {
            while(1)
            {
                if(pos!=vis[u]&&vis[fa]!=pos){
                    vis[e]=pos;
                    pos++;
                    break;
                }
                pos++;
            }
            cot=max(cot,pos-1);
            dfs(e,u);
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++){
        int x,y;scanf("%d%d",&x,&y);
        addedge(x,y);
        in[x]++;in[y]++;
    }
    vis[1]=1;
    dfs(1,1);
    cout<<cot<<endl;
    for(int i=1;i<=n;i++) cout<<vis[i]<<" ";
}

总结：这题想了好久(接近三个小时..)，看出来还需要加油啊！