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.

Source: codeforces | Difficulty: MEDIUM


Solutions:
import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(x, y) = gil()
	adj[x].append(y)
	adj[y].append(x)
used = set()
clr = [0] * (n + 1)
maxVal = 1
toClr = []
st = [1]
vis = [0] * (n + 1)
while st:
	i = st.pop()
	if vis[i]:
		continue
	vis[i] = 1
	ptr = 1
	used.add(clr[i])
	if clr[i] == 0:
		toClr.append(i)
	for y in adj[i]:
		if clr[y]:
			used.add(clr[y])
		else:
			st.append(y)
			toClr.append(y)
	while toClr:
		while ptr in used:
			ptr += 1
		used.add(ptr)
		clr[toClr.pop()] = ptr
		maxVal = max(maxVal, ptr)
		ptr += 1
	used.clear()
print(maxVal)
print(*clr[1:])


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		col = [0] * (n + 1)
		col[0] = INF
		col[1] = 1
		par = [0] * (n + 1)
		graph = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(x, y) = ria()
			graph[x].append(y)
			graph[y].append(x)

		def dfs():
			mxc = 1
			visited = [False] * (n + 1)
			start = 1
			stack = [start]
			while stack:
				start = stack[-1]
				if not visited[start]:
					visited[start] = True
					(a, b) = (col[par[start]], col[start])
					ind = 1
					for child in graph[start]:
						if not visited[child]:
							par[child] = start
							while ind != len(graph[start]) + 2:
								if ind != a and ind != b:
									col[child] = ind
									mxc = max(mxc, ind)
									ind += 1
									break
								ind += 1
							stack.append(child)
				else:
					stack.pop()
			return mxc
		wi(dfs())
		wia(col[1:])
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


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()


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List, Mapping
sys.setrecursionlimit(999999)
cs = [0, 1] + [0] * 10 ** 6
n = int(input())
g = collections.defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
q = collections.deque([[1, 0]])
while q:
	(cur, fa) = q.popleft()
	s = set()
	s.add(cs[cur])
	if fa:
		s.add(cs[fa])
	k = 1
	for nc in g[cur]:
		if nc == fa:
			continue
		while k in s:
			k += 1
		cs[nc] = k
		s.add(k)
		q.append([nc, cur])
print(max(cs[1:n + 1]))
print(*cs[1:n + 1])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	graph = col.defaultdict(set)
	for n in range(N - 1):
		(U, V) = getInts()
		U -= 1
		V -= 1
		graph[U].add(V)
		graph[V].add(U)

	def bfs(node):
		import collections as col
		nodes.remove(node)
		cols[node] = 1
		queue = col.deque([])
		queue.append((node, 1, -1, -1))
		while queue:
			(node, colour, parent, parent_col) = queue.popleft()
			y = set([j + 1 for j in range(len(graph[node]) + 1)])
			if colour in y:
				y.remove(colour)
			if parent_col in y:
				y.remove(parent_col)
			for neighbour in graph[node]:
				if neighbour in nodes:
					nodes.remove(neighbour)
					new_col = next(iter(y))
					y.remove(new_col)
					cols[neighbour] = new_col
					queue.append((neighbour, new_col, node, colour))
		return
	nodes = set([j for j in range(N)])
	cols = [-1] * N
	bfs(0)
	print(max(cols))
	print(*cols)
	return
solve()


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]

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
			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)
initialize()
bfs(1)
print(max(color))
c_string = ''
for i in range(1, n + 1):
	c_string += str(color[i]) + ' '
print(c_string)


n = int(input())
from collections import defaultdict, deque
g = defaultdict(list)
from sys import stdin
for i in range(n - 1):
	(h, m) = 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
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)


n = int(input())
g = [[] for i 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)
l = 0
for i in range(n):
	l = max(l, len(g[i]) + 1)
q = [0]
paint = [-1] * n
paint[0] = 1
while q:
	ver = q.pop()
	use = set()
	use.add(paint[ver])
	for to in g[ver]:
		use.add(paint[to])
	arr = []
	for i in range(1, l + 1):
		if not i in use:
			arr.append(i)
		if len(arr) == len(g[ver]):
			break
	for to in g[ver]:
		if paint[to] == -1:
			for j in range(1, l + 1):
				if not j in use:
					paint[to] = arr[-1]
					q.append(to)
					arr.pop()
					break
print(l)
print(*paint)


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)))


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) = 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:])))
main()


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)))


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(v, s):
	V[v] = True
	c = 1
	for _ in X[v]:
		if not V[_]:
			while c in s:
				c += 1
			C[_] = c
			c += 1
	for _ in X[v]:
		if not V[_]:
			yield dfs(_, set({C[v], C[_]}))
	yield
n = INI()
X = [[] for _ in range(n + 1)]
V = [False for _ in range(n + 1)]
C = [0 for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = INL()
	X[u].append(v)
	X[v].append(u)
C[1] = 1
dfs(1, set({1}))
OPS(len(set(C)) - 1)
OPL(C[1:])


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)))


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 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:])


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

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)))


import sys

def input():
	return sys.stdin.buffer.readline().strip()
n = int(input())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
cl = [0] * (n + 1)
par = [0] * (n + 1)

def dfs(adj, i):
	vis = [0] * (n + 1)
	q = [i]
	cl[1] = 1
	while len(q) > 0:
		u = q[-1]
		if vis[u] == 0:
			vis[u] = 1
			c = 1
			for v in adj[u]:
				if vis[v] == 0:
					while c == cl[u] or c == cl[par[u]]:
						c += 1
					cl[v] = c
					par[v] = u
					c += 1
					q.append(v)
		else:
			q.pop()
m = 0
for i in range(1, n + 1):
	m = max(m, len(adj[i]) + 1)
print(m)
dfs(adj, 1)
for i in range(1, n + 1):
	print(cl[i], end=' ')


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:]))))


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()
	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)


import sys
from collections import defaultdict
from collections import deque
from types import GeneratorType
input = sys.stdin.readline

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def get_adj_mat(src, dst):
	matrix = defaultdict(list)
	for (src_i, dst_i) in zip(src, dst):
		matrix[src_i].append(dst_i)
		matrix[dst_i].append(src_i)
	return matrix

@bootstrap
def set_colour(curr_index, parent_index, adj_mat, colours):
	val = 1
	(curr_val, parent_val) = (colours[curr_index], colours[parent_index])
	for child_index in adj_mat[curr_index]:
		if child_index != parent_index:
			while val in [curr_val, parent_val]:
				val += 1
			colours[child_index] = val
			val += 1
			yield set_colour(child_index, curr_index, adj_mat, colours)
	yield None

def solve(src, dst, n):
	adj_mat = get_adj_mat(src, dst)
	colours = [-1] * n
	root = 0
	colours[root] = 1
	set_colour(0, 0, adj_mat, colours)
	print(max(colours))
	print(*colours)
n = int(input())
(src, dst) = ([], [])
for _ in range(n - 1):
	(src_i, dst_i) = [int(val) for val in input().split()]
	(src.append(src_i - 1), dst.append(dst_i - 1))
solve(src, dst, n)


from sys import stdin

def main():
	n = int(input()) + 1
	g = [[] for _ in range(n)]
	for s in stdin.read().splitlines():
		(u, v) = map(int, s.split())
		g[u].append(v)
		g[v].append(u)
	(cc, palette, nxt) = ([0] * n, [True] * n, [(1, 0, 1)])
	cc[1] = 1
	while nxt:
		(cur, nxt) = (nxt, [])
		for (u, a, b) in cur:
			palette[a] = palette[b] = False
			c = 1
			for v in g[u]:
				if not cc[v]:
					while not palette[c]:
						c += 1
					cc[v] = c
					nxt.append((v, b, c))
					c += 1
			palette[a] = palette[b] = True
	print(max(cc))
	print(' '.join(map(str, cc[1:])))
main()


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:])


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=' ')