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·10^5) — 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 


-----Note-----

In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct. [Image] Illustration for the first sample. 

In the second example there are following triples of consequently connected squares:   1 → 3 → 2  1 → 3 → 4  1 → 3 → 5  2 → 3 → 4  2 → 3 → 5  4 → 3 → 5  We can see that each pair of squares is encountered in some triple, so all colors have to be distinct. [Image] Illustration for the second sample. 

In the third example there are following triples:   1 → 2 → 3  2 → 3 → 4  3 → 4 → 5  We can see that one or two colors is not enough, but there is an answer that uses three colors only. [Image] Illustration for the third sample.

Difficulty: interview

Starter code:

Solutions:
import sys
sys.setrecursionlimit(200000)

n = int(input())
arr = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    arr[a - 1].append(b - 1)
    arr[b - 1].append(a - 1)
s = max([len(p) for p in arr]) + 1
print(s)

colored = [0] * n
def dfs(v, c, d):
    colored[v] = p = c
    for u in arr[v]:
        if not colored[u]:
            c = c + 1 if c < s else 1
            if c == d:
                c = c + 1 if c < s else 1
            dfs(u, c, p)
if s > 3:
    dfs(0, 1, 0)
else:
    i = 0
    c = 1
    while len(arr[i]) != 1:
        i += 1
    for j in range(n):
        colored[i] = c
        c = c + 1 if c < s else 1
        if j < n - 1:
            i = arr[i][0] if not colored[arr[i][0]] else arr[i][1]
print(" ".join(map(str, colored)))

import sys
sys.setrecursionlimit(200000)

n = int(input())
arr = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    arr[a - 1].append(b - 1)
    arr[b - 1].append(a - 1)
s = max([len(p) for p in arr]) + 1
print(s)

colored = [0] * n
def dfs(v, c, d):
    colored[v] = p = c
    for u in arr[v]:
        if not colored[u]:
            c = c + 1 if c < s else 1
            if c == d:
                c = c + 1 if c < s else 1
            dfs(u, c, p)
if s > 3:
    dfs(0, 1, 0)
else:
    i = 0
    c = 1
    while len(arr[i]) != 1:
        i += 1
    for j in range(n):
        colored[i] = c
        c = c + 1 if c < s else 1
        if j < n - 1:
            i = arr[i][0] if not colored[arr[i][0]] else arr[i][1]
print(" ".join(map(str, colored)))

import sys
sys.setrecursionlimit(200000)

n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
s = max([len(p) for p in g]) + 1
print(s)
r=[0]*n
def dfs(v,c,d):
    r[v]=p=c
    for u in g[v]:
        if not r[u]:
            c=c+1 if c<s else 1
            if c==d:
                c=c+1 if c<s else 1
            dfs(u,c,p)
if s>3:
    dfs(0, 1, 0)
else:
    i=0
    c=1
    while len(g[i])!=1:
        i+=1
    for j in range(n):
        r[i]=c
        c=c+1 if c<s else 1
        if j<n-1:
            i=g[i][0] if not r[g[i][0]] else g[i][1]
print(" ".join(map(str, r)))

#!/usr/bin/env python3

from collections import deque



def ri():

    return list(map(int, input().split()))



n = int(input())

v = [0]*n

c = [0]*n

p = [0]*n

adj = [set() for i in range(n)]

for i in range(n-1):

    a, b = ri()

    a -= 1

    b -= 1

    adj[a].add(b)

    adj[b].add(a)

for s in range(n):

    if len(adj[s]) == 1:

        break

ans = 0

q = deque()

q.append(s)

v[s] = 1

c[s] = 1

p[s] = s

while q:

    n = q.popleft()

    cc = 1

    for a in adj[n]:

        if v[a] == 0:

            while cc in [c[n], c[p[n]]]:

                cc+=1

            c[a] = cc

            cc+=1

            ans = max(2+len(adj[a])-1, ans)

            q.append(a)

            p[a] = n

            v[a] = 1

print(ans)

print(" ".join(map(str,c)))





# Made By Mostafa_Khaled


from sys import stdin
from collections import deque


def main():
    n = int(input()) + 1
    g = [[] for _ in range(n)]
    for s in range(n-2):
        u, v = list(map(int, input().split()))
        g[u].append(v)
        g[v].append(u)
    cc, palette, q = [0] * n, [True] * n, deque(((1, 0, 1),))
    cc[1] = 1
    while q:
        u, a, b = q.popleft()
        
        c = 1
        for v in g[u]:
            if not cc[v]:
                while c in [a,b]:
                    c += 1
                cc[v] = c
                q.append((v, b, c))
                c += 1
        
    print(max(cc))
    print(' '.join(map(str, cc[1:])))


def __starting_point():
    main()
        

__starting_point()

from collections import deque

n = int(input())

ans = [0]*n

g = [[]for _ in range(n)]

for _ in range(n - 1):
  u, v = list(map(int, input().split()))
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

col = 1
q = deque()
vis = [False]*n

q.append((0, 0))
vis[0] = True
ans[0] = 1
p_top = 0

while q:
  top, p_top = q.popleft()
  col = 1
  for viz in g[top]:
    if not vis[viz]:
      vis[viz] = True
      q.append((viz, top))
      while ans[top] == col or ans[p_top] == col:
        col += 1
      ans[viz] = col
      col += 1

print(max(ans))
print(" ".join(map(str, ans)))


import collections
def doit():
    # rows = [[] for y in range(M)]
    rows = dict()

    N = int(input())
    graph = dict()
    for n in range(N) :
        graph[n] = list()

    for n in range(N - 1):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    msize = 0
    for k in graph:
        msize = max(msize, len(graph[k]))
    print(msize+1)


    root = 0
    colors = [0 for x in range(N)]
    colors[root] = 1
    parents = [0 for x in range(N)]
    parents[root] = root


    def color(c1, c2):
        colorindex = 0
        while colorindex < msize + 1:
            colorindex += 1
            if colorindex == c1 or colorindex == c2:
                continue
            yield colorindex


    # visited = set()
    # visited.add(root)
    queue = collections.deque([root])
    while queue:
        vertex = queue.popleft()
        # newcolors = [c for c in range(1, msize+2) if c != colors[vertex] and c != colors[parents[vertex]] ]
        # newcolors = filter(lambda c: c != colors[vertex] and c != colors[parents[vertex]], range(1, msize+2))
        #
        # print(f'newcolors={newcolors}')
        colorgen = color(colors[vertex], colors[parents[vertex]])
        for neighbour in graph[vertex]:
            if neighbour == parents[vertex]:
                continue
            parents[neighbour] = vertex
            colors[neighbour] = next(colorgen)
            # visited.add(neighbour)
            queue.append(neighbour)
    print(" ".join(map(str, colors)))

doit()

import collections
def doit():
    N = int(input())
    graph = dict()
    for n in range(N) :
        graph[n] = list()

    for n in range(N - 1):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    msize = 0
    for k in graph:
        msize = max(msize, len(graph[k]))
    print(msize+1)

    root = 0

    colors = [0 for x in range(N)]
    colors[root] = 1
    parents = [0 for x in range(N)]
    parents[root] = root

    def colorgenerator(c1, c2):
        colorindex = 0
        while colorindex < msize + 1:
            colorindex += 1
            if colorindex == c1 or colorindex == c2:
                continue
            yield colorindex

    queue = collections.deque([root])
    while queue:
        vertex = queue.popleft()
        color = colorgenerator(colors[vertex], colors[parents[vertex]])
        for neighbour in graph[vertex]:
            if neighbour == parents[vertex]:
                continue

            parents[neighbour] = vertex
            colors[neighbour] = next(color)
            queue.append(neighbour)
    print(" ".join(map(str, colors)))

doit()

from collections import deque

n = int(input())
g = []
visited = []
color = []
max_child_color = []
parent = []

def initialize():
    for i in range(n+10):
        g.append([])
        visited.append(False)
        color.append(0)
        max_child_color.append(0)
        parent.append(0)
    for i in range(n-1):
        u, v = map(int, input().split())
        g[u] += [v]
        g[v] += [u]
    # print(g)

def get_color(u):
    for i in range(max_child_color[u]+1, n+1):
        if i != color[parent[u]] and i != color[u]:
            max_child_color[u] = i
            # print(f'Setting max child color of node = {u} to color {i}')
            return i

def bfs(start):
    visited[start] = True
    color[start] = 1
    q = deque()
    q.append(start)
    while q:
        u = q.popleft()
        for v in g[u]:
            parent[v] = u
            if not visited[v]:
                visited[v] = True
                color[v] = get_color(u)
                q.append(v)

def __starting_point():
    initialize()
    bfs(1)
    print(max(color))
    c_string = ""
    for i in range(1, n+1):
        c_string += str(color[i]) + " "
    print(c_string)
__starting_point()

import sys
sys.setrecursionlimit(100000)
from collections import deque

UNDEF = 0

n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
c = [UNDEF] * (n + 1)
c[1] = 1

def dfs(par, v):
    cur = 1
    for to in g[v]:
        if c[to] != UNDEF:
            continue
        while cur in (c[par], c[v]):
            cur += 1
        c[to] = cur
        cur += 1
        dfs(v, to)

def bfs():
    q = deque([(0, 1)])
    while q:
        cur = 1
        par, v = q.pop()
        for to in g[v]:
            if c[to] != UNDEF:
                continue
            while cur in (c[par], c[v]):
                cur += 1
            c[to] = cur
            cur += 1
            q.appendleft((v, to))

bfs()
print('%d\n%s' % (max(c), ' '.join(map(str, c[1:]))))

import sys
input = sys.stdin.readline
from collections import deque

def bfs():
    visited = [False]*n
    visited[0] = True
    color = [-1]*n
    color[0] = 1
    q = deque([(0, 1, -1)])

    while q:
        v, pre_c1, pre_c2 = q.popleft()
        cnt = 1
        
        for nv in G[v]:
            if visited[nv]:
                continue
            
            while cnt==pre_c1 or cnt==pre_c2:
                cnt += 1
            
            color[nv] = cnt
            cnt += 1
            q.append((nv, color[v], color[nv]))
            visited[nv] = True
    
    return color

n = int(input())
G = [[] for _ in range(n)]

for _ in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)

color = bfs()

print(max(color))
print(*color)

from collections import defaultdict,deque
class Graph:
    def __init__(self,n):
        self.graph = defaultdict(list)
        self.parentColor = [-1] * (n+1)
        self.color = [-1] * (n+1)
        self.visited = [False] * (n+1)
        self.n = n
    def addEdge(self,fr,to):
        self.graph[fr].append(to)
        self.graph[to].append(fr) 
    def BFS(self,root):
        queue = deque()
        queue.append(root)
        self.color[root] = 1
        self.parentColor[root] = 0
        while(queue):
            s = queue.popleft()
            Set = defaultdict(bool)
            Set[self.color[s]] = True
            Set[self.parentColor[s]] = True
            culur = 1
            for i in self.graph[s]:
                if(self.visited[i] == False):
                    queue.append(i)
                    self.parentColor[i] = self.color[s]
                    while(1):
                        if(not Set[culur]):
                            self.color[i] = culur
                            culur+=1
                            break
                        culur+=1
            self.visited[s] = True
    def show(self):
        print(max(self.color))
        print(*self.color[1:])

n = int(input())
G = Graph(n)
for _ in range(n-1):
    a,b = map(int,input().split())
    G.addEdge(a,b)
G.BFS(1)
G.show()

from collections import deque
n = int(input())
dic = {}
for i in range(n):
	dic[i]=[]
for i in range(n-1):
	a,b = map(int,input().split())
	dic[a-1].append(b-1)
	dic[b-1].append(a-1)
color = {}
prevcolor = {}
color[0] = 1
prevcolor[0] = 1
lis = deque()
lis.append(0)
visited = {}
while(len(lis)!=0):
	t = lis.popleft()
	col = 0
	visited[t] = 1
	prev = prevcolor[t]
	for i in dic[t]:
		try:
			z = visited[i]
		except:
			while(col==prev or col==color[t] or col==prevcolor[t]):
				col+=1
			color[i] = col
			prevcolor[i] = color[t]
			lis.append(i)
			prev = col

print(max(color.values())+1)
for i in range(n):
	print(color[i]+1,end=" ")

import sys
sys.setrecursionlimit(200000)
 
n = int(input())
arr = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    arr[a - 1].append(b - 1)
    arr[b - 1].append(a - 1)
s = max([len(p) for p in arr]) + 1
print(s)
 
colored = [0] * n
def dfs(v, c, d):
    colored[v] = p = c
    for u in arr[v]:
        if not colored[u]:
            c = c + 1 if c < s else 1
            if c == d:
                c = c + 1 if c < s else 1
            dfs(u, c, p)
if s > 3:
    dfs(0, 1, 0)
else:
    i = 0
    c = 1
    while len(arr[i]) != 1:
        i += 1
    for j in range(n):
        colored[i] = c
        c = c + 1 if c < s else 1
        if j < n - 1:
            i = arr[i][0] if not colored[arr[i][0]] else arr[i][1]
print(" ".join(map(str, colored)))

n = int(input())
arr = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    arr[a - 1].append(b - 1)
    arr[b - 1].append(a - 1)
s = max([len(p) for p in arr]) + 1
print(s)
 
colored = [0] * n
def dfs(v, c, d):
    colored[v] = p = c
    for u in arr[v]:
        if not colored[u]:
            c = c + 1 if c < s else 1
            if c == d:
                c = c + 1 if c < s else 1
            dfs(u, c, p)
if s > 3:
    dfs(0, 1, 0)
else:
    i = 0
    c = 1
    while len(arr[i]) != 1:
        i += 1
    for j in range(n):
        colored[i] = c
        c = c + 1 if c < s else 1
        if j < n - 1:
            i = arr[i][0] if not colored[arr[i][0]] else arr[i][1]
print(" ".join(map(str, colored)))

import sys
n = int(sys.stdin.readline())
e = dict()
w = dict()
for i in range(1, n+1):
    w[i] = -1
    e[i] = set()

for i in range(n-1):
    (a, b) = map(int, sys.stdin.readline().split())
    e[a].add(b)
    e[b].add(a)



first = 0
for i in e:
    if len(e[i]) == 1:
        first = i
        break


sosed = set()
posetil = set()
sosed.add(first)
posetil.add(first)
w[first] = 1

while len(sosed) > 0:
    sosed2 = set()
    for i in sosed:
        NO = set()
        NO.add(w[i])
        bad = set()
        for j in e[i]:
            if len(e[j]) > 1:
                sosed2.add(j)
            if w[j] != -1:
                NO.add(w[j])
            else:
                bad.add(j)
        x = 1
        for j in bad:
            if w[j] == -1:
                while x in NO:
                    x += 1
                w[j] = x
                NO.add(x)
        posetil.add(i)
    sosed2 -= posetil
    sosed = sosed2.copy()
ans = []
lol = set()
for i in range(1, n+1):
    ans.append(w[i])
    lol.add(w[i])
print(len(lol))
print(*ans)

from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
n=int(input())
graph={i:set() for i in range(n)}
for i in range(n-1):
	a,b=list(map(int,input().split()))
	graph[a-1].add(b-1)
	graph[b-1].add(a-1)
ma=0
for i in graph:
	if len(graph[i])+1>ma:
		ma=len(graph[i])+1
		x=i
print(ma)
ans=[0 for i in range(n)]
stack=[x]
papa=[0 for i in range(n)]
while stack:
	x=stack.pop()
	# z=set(s)
	a=1
	if ans[x]==0:
		ans[x]=1
		z=[1]
	else:
		z=[]
		z.append(ans[x])
		z.append(ans[papa[x]])
	for j in graph[x]:
		while 1:
			if a in z:
				a+=1
			else:
				ans[j]=a
				a+=1
				break
		stack.append(j)
		graph[j].remove(x)
		papa[j]=x
print(*ans)


from sys import stdin
input = stdin.readline

def put():
    return map(int, input().split())

def dfs():
    s = [(0,0)]
    tree[0].append(1)
    while s:
        i,p = s.pop()
        c = 1
        for j in tree[i]:
            if j!=p:
                s.append((j,i))
                while c in [color[i], color[p]]:
                    c+=1
                color[j]=c
                c+=1
                


n = int(input())
tree = [[] for i in range(n+1)]
color= [0]*(n+1)
for _ in range(n-1):
    x,y = put()
    tree[x].append(y)
    tree[y].append(x)

ans = 0
for i in range(1,n+1):
    ans = max(ans, len(tree[i])+1)

dfs()
print(ans)
print(*color[1:])

n=int(input())
from collections import defaultdict,deque
g=defaultdict(list)
from sys import stdin
for i in range(n-1):
    h,m=list(map(int, stdin.readline().split()))
    g[h-1].append(m-1)
    g[m-1].append(h-1)
vis=[0]*n
c=[0]*n
c[0]=1
q=deque()
q.append(0)
while q:
    node=q.popleft()
    vis[node]=1
    s=set()
    for i in g[node]:
        if vis[i]==1:
            s.add(c[i])
    p=[]
    s.add(c[node])
    l=len(s)
    j=0
    k=1
    while l+j<=len(g[node])+2:
        r=0
        while r==0:
            if k not in s:
                p.append(k)
                r=1
            k+=1
        j+=1
    j=0
    for i in g[node]:
        if vis[i]==0:
            c[i]=p[j]
            j+=1
            q.append(i)

print(max(c))
print(*c)
        
            


n=int(input())
from collections import defaultdict,deque
g=defaultdict(list)
from sys import stdin
for i in range(n-1):
    h,m=list(map(int, stdin.readline().split()))
    g[h-1].append(m-1)
    g[m-1].append(h-1)
vis=[0]*n
c=[0]*n
c[0]=1
q=deque()
q.append(0)
while q:
    node=q.popleft()
    vis[node]=1
    s=set()
    for i in g[node]:
        if vis[i]==1:
            s.add(c[i])
    p=[]
    s.add(c[node])
    l=len(s)
    j=0
    k=1
    while l+j<=len(g[node])+2:
        r=0
        while r==0:
            if k not in s:
                p.append(k)
                r=1
            k+=1
        j+=1
    j=0
    for i in g[node]:
        if vis[i]==0:
            c[i]=p[j]
            j+=1
            q.append(i)

print(max(c))
print(*c)
        
            


import sys
input = sys.stdin.readline
def dfs():
    stack = [(0,0)]
    d[0].append(1)
    while stack:
        i,p = stack.pop()
        c = 1
        for j in d[i]:
            if j != p:
                stack.append((j,i))
                while c in {color[i],color[p]}:
                    c = c+1

                color[j] = c
                c = c+1


n = int(input())
d = {}
d[0] = []
for _ in range(n-1):
    x,y = map(int,input().split())
    if x in d:
        d[x].append(y)

    else:
        d[x] = [y]

    if y in d:
        d[y].append(x)

    else:
        d[y] = [x]

m = 0
for i in d:
    if len(d[i]) > m:
        m = len(d[i])

ans = m+1
color = [-1]*(n+1)
dfs()
print(ans)
print(*color[1:])