AtCoder Beginner Contest 146 - Coloring Edges on Tree

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.
Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

-----Constraints-----
 -  2 \le N \le 10^5
 -  1 \le a_i \lt b_i \le N
 - All values in input are integers.
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

-----Output-----
Print N lines.
The first line should contain K, the number of colors used.
The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

-----Sample Input-----
3
1 2
2 3

-----Sample Output-----
2
1
2

Source: atcoder | Difficulty: MEDIUM


Solutions:
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append((b - 1, i))
	edge[b - 1].append((a - 1, i))
k = max((len(e) for e in edge))
print(k)
ans = [-1] * (n - 1)

def dfs(v=0, p=-1, to_p_col=-1):
	col = 1
	for (u, idx) in edge[v]:
		if u != p:
			if col == to_p_col:
				col += 1
			ans[idx] = col
			dfs(u, v, col)
			col += 1
dfs()
print('\n'.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	t[a].append(b)
	t[b].append(a)
	ab.append((min(a, b), max(a, b)))
k = max(map(len, t))
d = {}

def dfs(pre, cur, col):
	cn = 1 if col != 1 else 2
	for i in t[cur]:
		if i == pre:
			continue
		d[min(i, cur), max(i, cur)] = cn
		dfs(cur, i, cn)
		cn += 1
		if col == cn:
			cn += 1
dfs(0, 0, 0)
print(k)
for i in ab:
	print(d[i])


import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N + 1)]
for n in range(N - 1):
	(a, b) = map(int, input().split())
	E[a].append((b, n))
	E[b].append((a, n))
K = max((len(e) for e in E))
print(K)
res = [-1 for _ in range(N - 1)]

def dfs(v=1, p=0, p_col=-1):
	col = 1
	for (child, idx) in E[v]:
		if child != p:
			if col == p_col:
				col += 1
			res[idx] = col
			dfs(child, v, col)
			col += 1
dfs()
print('\n'.join(map(str, res)))


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
INF = 1 << 50
EPS = 1e-08
mod = 10 ** 9 + 7

def mapline(t=int):
	return list(map(t, sysread().split()))

def mapread(t=int):
	return list(map(t, read().split()))

def dfs(c, to, cols, max_counts, pre_col=0):
	colors = set()
	colors.add(pre_col)
	num = 1
	for (idx, n) in to[c]:
		if cols[idx]:
			continue
		for i in range(num, max_counts + 1):
			if not i in colors:
				num = i
				cols[idx] = i
				colors.add(i)
				dfs(n, to, cols, max_counts, i)
				break

def run():
	N = int(sysread())
	to = [[] for _ in range(N + 1)]
	cols = [0] * (N - 1)
	counts = [0 for i in range(N + 1)]
	for i in range(N - 1):
		(a, b) = mapline()
		to[a].append((i, b))
		to[b].append((i, a))
		counts[a] += 1
		counts[b] += 1
	max_counts = max(counts)
	print(max_counts)
	dfs(1, to, cols, max_counts)
	for c in cols:
		print(c)

def __starting_point():
	run()
__starting_point()


import sys
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 9)
n = int(input())
e = [[] for i in range(1 + n)]
ei = {}
for i in range(n - 1):
	(_, __) = map(int, input().split())
	e[_].append(__)
	e[__].append(_)
	ei[_, __] = i
	ei[__, _] = i
M = max([len(x) for x in e])
res = [0] * (n - 1)
from collections import deque
dq = deque([])
Ms = [1] * (1 + n)
dq.append(1)
while dq:
	now = dq.popleft()
	for ne in e[now]:
		ind = ei[ne, now]
		if res[ind] == 0:
			res[ind] = Ms[now]
			Ms[now] = Ms[now] % M + 1
			Ms[ne] = Ms[now]
			dq.append(ne)
print(M)
print(*res, sep='\n')


N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append((b, i))
	G[b].append((a, i))
ans = [-1] * (N - 1)
cmx = 0
stk = [0]
while stk:
	v = stk.pop()
	cs = set()
	for (to, toi) in G[v]:
		if ans[toi] >= 0:
			cs.add(ans[toi])
	c = 1
	for (to, toi) in G[v]:
		if ans[toi] >= 0:
			continue
		while c in cs:
			c += 1
		ans[toi] = c
		cmx = max(cmx, c)
		cs.add(c)
		stk.append(to)
print(cmx)
for a in ans:
	print(a)


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
to = [[] for i in range(n)]
edge = {}
color = [0] * (n - 1)
for i in range(1, n):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	to[a].append(b)
	to[b].append(a)
	edge[a, b] = edge[b, a] = i

def dfs(n, b=-1, bc=-1):
	to_n = to[n]
	k = 1
	for i in range(len(to_n)):
		if to_n[i] == b:
			continue
		if k == bc:
			k += 1
		color[edge[n, to_n[i]] - 1] = k
		dfs(to_n[i], n, k)
		k += 1
dfs(0)
print(max(color))
for i in range(n - 1):
	print(color[i])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
E = []
T = [[] for i in range(N)]
for (i, n) in enumerate(range(N - 1)):
	(a, b) = map(int, input().split())
	E.append((a - 1, b - 1))
	T[a - 1].append(b - 1)
R = [None for i in range(N)]

def dfs(using, cur):
	R[cur] = using
	i = 0
	for t in T[cur]:
		if i == using:
			i += 1
		dfs(i, t)
		i += 1
dfs(-1, 0)
print(max(R) + 1)
for e in E:
	print(R[e[1]] + 1)


from collections import deque

def main():
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	for i in range(1, n):
		(a, b) = map(int, input().split())
		d1 = {'id': i, 'to': b}
		d2 = {'id': i, 'to': a}
		graph[a].append(d1)
		graph[b].append(d2)
	k = 0
	root = 1
	for i in range(1, n + 1):
		if k < len(graph[i]):
			root = i
			k = max(k, len(graph[i]))
	print(k)
	q = deque([root])
	color = [[] for _ in range(n + 1)]
	reached = [False] * (n + 1)
	ans = [0] * n
	while q:
		current = q.popleft()
		reached[current] = True
		temp = 1
		for dic in graph[current]:
			id = dic['id']
			next = dic['to']
			if reached[next]:
				continue
			while temp in color[current]:
				temp += 1
			color[next].append(temp)
			ans[id] = temp
			temp += 1
			q.append(next)
	for i in ans[1:]:
		print(i)

def __starting_point():
	main()
__starting_point()


from collections import deque
n = int(input())
E = [[] for _ in range(n + 1)]
edge_order = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	E[a].append(b)
	edge_order.append(b)
q = deque([1])
color = [0] * (n + 1)
while q:
	V = q.popleft()
	c = 1
	for nv in E[V]:
		if c == color[V]:
			c += 1
		color[nv] = c
		c += 1
		q.append(nv)
print(max(color))
for i in edge_order:
	print(color[i])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append([b, i])
ans = [None] * (n - 1)

def rec(cur, color):
	cnt = 1
	for (to, j) in G[cur]:
		if cnt == color:
			cnt += 1
		ans[j] = cnt
		rec(to, cnt)
		cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep='\n')


N = int(input())
ip = []
hen = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	ip.append([a, b])
	hen[a].append(b)
p = [-1] * N
for i in range(N):
	x = 0
	for (j, h) in enumerate(hen[i]):
		if p[i] == j:
			x += 1
		p[h] = j + x
print(max(p) + 1)
for i in range(N - 1):
	print(p[ip[i][1]] + 1)


from collections import deque
n = int(input())
ab = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ab[a].append([b, i])
que = deque()
que.append(1)
visited = [0] * n
ans = [0] * (n - 1)
while que:
	x = que.popleft()
	k = 1
	for j in ab[x]:
		if visited[x - 1] != k:
			ans[j[1]] += k
			visited[j[0] - 1] += k
			k += 1
			que.append(j[0])
		else:
			ans[j[1]] += k + 1
			visited[j[0] - 1] += k + 1
			k += 2
			que.append(j[0])
print(max(ans))
for l in ans:
	print(l)


N = int(input())
edges = [[] for i in range(N)]
ans = [-1] * (N - 1)
lines = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	lines.append((a, b))
	edges[a - 1].append((b - 1, i))
q = [(0, 0)]
max_color = 0
while q:
	(v, c) = q.pop()
	color = 1
	if c == color:
		color += 1
	for (nv, i) in edges[v]:
		ans[i] = color
		q.append((nv, color))
		color += 1
		if c == color:
			color += 1
print(max(ans))
for i in range(N - 1):
	(a, b) = lines[i]
	print(ans[i])


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
n = int(input())
t = [list(map(int, input().split())) for _ in range(n - 1)]
hands = [0 for _ in range(n + 1)]
for (a, b) in t:
	hands[a] += 1
	hands[b] += 1
number_of_colors = max(*hands)

def next_color(i):
	return i + 1 if i < number_of_colors else 1

class edge:

	def __init__(self, en):
		self.ends = en
		self.color = 0

	def set_color(self, co):
		self.color = co

class nord:

	def __init__(self, tr):
		self.parent = tr
		self.edges = []

	def add(self, ed):
		self.edges.append(ed)

	def set_color(self, previous_color):
		co = next_color(previous_color)
		for ed in self.edges:
			if ed.color == 0:
				ed.set_color(co)
				for i in ed.ends:
					no = self.parent.nords[i - 1]
					if self is not no:
						no.set_color(co)
				co = next_color(co)

class tree:

	def __init__(self):
		self.nords = []

	def add_nord(self, no):
		self.nords.append(no)

	def add_edge(self, ed):
		for i in ed.ends:
			self.nords[i - 1].add(ed)

	def set_color(self):
		self.nords[0].set_color(0)
tr = tree()
for _ in range(n):
	no = nord(tr)
	tr.add_nord(no)
e_tree = []
for en in t:
	ed = edge(en)
	e_tree.append(ed)
	tr.add_edge(ed)
tr.set_color()
print(number_of_colors)
for e in e_tree:
	print(e.color)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 * 2)
n = int(input())
child = [[] for _ in range(n)]
color = [-1] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	child[a - 1].append((b - 1, i))

def f(now, parent_node):
	color_num = 1
	for (i, j) in child[now]:
		if color_num == parent_node:
			color_num += 1
		color[j] = color_num
		f(i, color_num)
		color_num += 1
f(0, 0)
print(max(color))
for x in color:
	print(x)


from collections import deque
N = int(input())
edge = [set() for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a].add((b, i))
	edge[b].add((a, i))
r = [0] * (N - 1)
q = deque([(0, 1)])
while q:
	(preC, fromv) = q.popleft()
	c = 0
	for (tov, i) in edge[fromv]:
		edge[tov].remove((fromv, i))
		c += 1 + (c + 1 == preC)
		q.append((c, tov))
		r[i] = c
print(max(r))
for x in r:
	print(x)


N = int(input())
l = [[] for i in range(N)]
color = [0] * N
mem = []
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	l[a].append(b)
	mem.append(b)
from collections import deque
que = deque([0])
while que:
	node = que.popleft()
	c = 1
	for i in l[node]:
		if color[node] == c:
			c += 1
		color[i] = c
		c += 1
		que.append(i)
print(max(color))
for i in mem:
	print(color[i])


import sys
sys.setrecursionlimit(200000)

def solve(N: int, a: 'List[int]', b: 'List[int]'):
	from itertools import count
	edges = [[] for _ in range(N)]
	for (i, (aa, bb)) in enumerate(zip(a, b)):
		edges[aa - 1].append((bb - 1, i))
		edges[bb - 1].append((aa - 1, i))
	ans = [None] * (N - 1)
	visited = set()

	def dfs(n, c):
		if n in visited:
			return
		visited.add(n)
		for ((nn, i), cc) in zip(filter(lambda x: x[0] not in visited, edges[n]), filter(lambda y: y != c, count(1))):
			ans[i] = cc
			dfs(nn, cc)
	dfs(0, None)
	return [max(ans)] + ans

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int()] * (N - 1)
	b = [int()] * (N - 1)
	for i in range(N - 1):
		a[i] = int(next(tokens))
		b[i] = int(next(tokens))
	print(*solve(N, a, b), sep='\n')

def test():
	import doctest
	doctest.testmod()

def __starting_point():
	main()
__starting_point()


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
child = [[] for _ in range(n)]
edge_order = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	child[a].append((i, b))
	edge_order.append(b)
queue = deque([0])
color = [0] * n
while queue:
	v = queue.popleft()
	c = 1
	for (i, u) in child[v]:
		if c == color[v]:
			c += 1
		color[u] = c
		c += 1
		queue.append(u)
print(max(color))
for i in edge_order:
	print(color[i])


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
A = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	A[a].append([b, i])
ans = [0] * (n - 1)

def col(now, color):
	c = 1
	for (b, j) in A[now]:
		if c == color:
			c += 1
		ans[j] = c
		col(b, c)
		c += 1
col(0, 0)
print(max(ans))
for a in ans:
	print(a)


import sys
sys.setrecursionlimit(10 ** 9)
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, i])
ans = [0] * (N - 1)

def func(prt, col):
	cnt = 1
	for (cld, org) in G[prt]:
		if cnt == col:
			cnt += 1
		ans[org] = cnt
		func(cld, cnt)
		cnt += 1
func(0, 0)
print(max(ans))
for i in range(N - 1):
	print(ans[i])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append([b, i])
ans = [None] * (n - 1)

def dfs(now, color):
	cnt = 1
	for (to, num) in g[now]:
		if cnt == color:
			cnt += 1
		ans[num] = cnt
		dfs(to, cnt)
		cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep='\n')


N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append((b - 1, i))
	E[b - 1].append((a - 1, i))
C = [0] * (N - 1)
stack = [0]
parent_e = [0] * N
max_c = 0
while stack:
	n = stack.pop()
	c = 1
	for (to, i) in E[n]:
		if n != 0 and parent_e[n] == i:
			continue
		c += 1 if n != 0 and C[parent_e[n]] == c else 0
		C[i] = c
		max_c = max(max_c, c)
		c += 1
		stack.append(to)
		parent_e[to] = i
print(max_c)
print('\n'.join(map(str, C)))


from collections import deque
n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	t[a].append((b, i))
q = deque([(0, 0)])
while q:
	(v, pc) = q.popleft()
	nc = 0
	for (nv, edge) in t[v]:
		nc += 1
		if nc == pc:
			nc += 1
		color[edge] = nc
		q.append((nv, nc))
print(max(color))
print(*color, sep='\n')


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
child = [[] for _ in range(N + 1)]
par = [0] * (N + 1)
for ab in AB:
	(a, b) = (ab[0], ab[1])
	child[a].append(b)
	par[b] = a
k = 0
for i in range(1, N + 1):
	l = len(child[i])
	if par[i] > 0:
		l += 1
	k = max(k, l)
print(k)
col = [0] * (N + 1)
col[1] = 1
for i in range(1, N):
	cnt = 0
	for c in child[i]:
		cnt += 1
		col[c] = (col[i] + cnt) % k
for ab in AB:
	b = ab[1]
	print(col[b] + 1)


from collections import deque
N = int(input())
B = []
L = []
for i in range(N - 1):
	(ta, tb) = map(int, input().split())
	B.append(ta)
	B.append(tb)
	L.append([ta, tb])
B = B[1::2]
E = [[] for _ in range(N + 1)]
for (a, b) in L:
	E[a].append(b)
Q = deque([1])
C = [0] * (N + 1)
while Q:
	v = Q.popleft()
	c = 0
	for u in E[v]:
		c += 1 + (c + 1 == C[v])
		C[u] = c
		Q.append(u)
print(max(C))
print('\n'.join((str(C[b]) for b in B)))


n = int(input())
ab = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ab.append([a, b])
graph = [[] for _ in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
root = 1
parent = [0] * (n + 1)
order = []
stack = [root]
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)
color = [-1] * (n + 1)
for x in order:
	ng = color[x]
	c = 1
	for y in graph[x]:
		if y == parent[x]:
			continue
		if c == ng:
			c += 1
		color[y] = c
		c += 1
print(max(color))
for (a, b) in ab:
	if parent[a] == b:
		print(color[a])
	else:
		print(color[b])


from collections import deque

def resolve():
	N = int(input())
	G = [[] for _ in range(N)]
	nextV = []
	for _ in range(N - 1):
		(a, b) = [int(x) - 1 for x in input().split()]
		G[a].append(b)
		nextV.append(b)
	q = deque()
	q.append(0)
	color = [0] * N
	while q:
		v = q.popleft()
		parentC = color[v]
		c = 1
		for to in G[v]:
			if c == parentC:
				c += 1
			color[to] = c
			c += 1
			q.append(to)
	print(max(color))
	for b in nextV:
		print(color[b])

def __starting_point():
	resolve()
__starting_point()


import sys
readline = sys.stdin.readline
N = int(readline())
G = [[] for i in range(N)]
from collections import defaultdict
E = defaultdict(int)
for i in range(N - 1):
	(a, b) = map(int, readline().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
	E[a - 1, b - 1] = i
from collections import deque
q = deque([])
ans = [None] * (N - 1)
q.append([0, -1, 0])
maxcol = 0
while q:
	(v, parent, color) = q.popleft()
	if color > maxcol:
		maxcol = color
	if (v, parent) in E:
		ans[E[v, parent]] = color
	elif (parent, v) in E:
		ans[E[parent, v]] = color
	next_col = 0
	for child in G[v]:
		if child == parent:
			continue
		next_col += 1
		if next_col == color:
			next_col += 1
		q.append([child, v, next_col])
print(maxcol)
for a in ans:
	print(a)


def main():
	N = int(input())
	vertex = [[] for i in range(N)]
	ini_v = 0
	for i in range(N - 1):
		(a, b) = [int(x) for x in input().split(' ')]
		if i == 0:
			ini_v = a - 1
		vertex[a - 1].append({'v': b - 1, 'e': i})
		vertex[b - 1].append({'v': a - 1, 'e': i})
	checked_v = [0] * N
	checked_e = [0] * (N - 1)
	to_visit = [ini_v]
	checked_v[ini_v] = 1
	color_e = [-1] * (N - 1)
	while len(to_visit):
		visiting = to_visit.pop(0)
		vs = vertex[visiting]
		used_cs = []
		cless_e = []
		for d in vs:
			if checked_v[d['v']] == 0:
				checked_v[d['v']] = 1
				to_visit.append(d['v'])
			if color_e[d['e']] == -1:
				cless_e.append(d['e'])
			else:
				used_cs.append(color_e[d['e']])
		s = 0
		for j in range(len(vs)):
			if s >= len(cless_e) or len(cless_e) == 0:
				break
			elif j in used_cs:
				continue
			else:
				color_e[cless_e[s]] = j
				s += 1
	print(max(color_e) + 1)
	for i in range(len(color_e)):
		print(color_e[i] + 1)
main()


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
s = [[] for i in range(n + 1)]
t = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	s[a - 1].append([b - 1, i])

def f(x, r):
	c = 1
	for (i, j) in s[x]:
		c += c == r
		t[j] = c
		f(i, c)
		c += 1
f(0, 0)
print(max(t))
for i in t:
	print(i)


n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	inp = list(map(int, input().split()))
	e[inp[0] - 1].append((inp[1] - 1, i))
	e[inp[1] - 1].append((inp[0] - 1, i))
col = [0 for i in range(n - 1)]
fl = [0 for i in range(n)]
s = [[0, 0]]
mc = 0
while len(s):
	ns = []
	for i in s:
		fl[i[0]] = 1
		cc = 1
		for j in e[i[0]]:
			if not fl[j[0]]:
				if cc == i[1]:
					cc += 1
				col[j[1]] = cc
				mc = max(mc, cc)
				ns.append([j[0], cc])
				cc += 1
	s = ns
print(mc)
for i in col:
	print(i)


import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
es = [[] for i in range(N)]
for (i, (a, b)) in enumerate(AB):
	(a, b) = (a - 1, b - 1)
	es[a].append((b, i))
	es[b].append((a, i))
visited = [0] * N
ans = [None] * (N - 1)

def dfs(v, c=-1):
	nc = 1
	for (to, i) in es[v]:
		if visited[to]:
			continue
		visited[v] = 1
		if nc == c:
			nc += 1
		ans[i] = nc
		dfs(to, nc)
		nc += 1
dfs(0)
print(max(ans))
print(*ans, sep='\n')


n = int(input())
vs = [[] for i in range(n)]
out = [0] * n
for i in range(n - 1):
	(a, b) = [int(i) - 1 for i in input().split()]
	vs[a].append([b, i + 1])
	vs[b].append([a, i + 1])
nex = [[0, -1]]

def coloring(index, defColor):
	i = 0
	for v in vs[index]:
		if i == defColor:
			i += 1
		out[v[1]] = i
		vs[v[0]].remove([index, v[1]])
		nex.append([v[0], i])
		i += 1
	out[0] = max(out[0], i - 1)
while nex.__len__() > 0:
	(c, d) = nex.pop()
	coloring(c, d)
for i in range(n):
	print(out[i] + 1)


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for i in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append((v, i))
	e[v].append((u, i))
res = [0] * (N - 1)

def dfs(x):
	global res
	c = 1
	vis = set()
	for (y, i) in e[x]:
		vis.add(res[i])
	for (y, i) in e[x]:
		if res[i] > 0:
			continue
		while c in vis:
			c += 1
		res[i] = c
		vis.add(c)
		dfs(y)
dfs(1)
print(max(res))
for r in res:
	print(r)


from collections import deque

def main():
	(N, *AB) = map(int, open(0).read().split())
	B = AB[1::2]
	E = [[] for _ in range(N + 1)]
	for (a, b) in zip(*[iter(AB)] * 2):
		E[a] += (b,)
	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q += (u,)
	print(max(C))
	for b in B:
		print(C[b])
main()


import sys
sys.setrecursionlimit(10010010)

def abc146_d():
	n = int(input())
	Q = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n - 1)]
	deg = [0] * n
	adj = [[] for _ in range(n)]
	color = dict()
	for (a, b) in Q:
		deg[a] += 1
		deg[b] += 1
		adj[a].append(b)
		adj[b].append(a)

	def dfs(s, p):
		nouse = -1
		if p > -1:
			nouse = color[min(s, p), max(s, p)]
		c = 1
		for t in adj[s]:
			if t == p:
				continue
			if c == nouse:
				c += 1
			color[min(s, t), max(s, t)] = c
			dfs(t, s)
			c += 1
	dfs(1, -1)
	print(max(deg))
	for (a, b) in Q:
		print(color[a, b])

def __starting_point():
	abc146_d()
__starting_point()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append((b - 1, i))
ans = [[] for _ in range(N - 1)]

def sub(p, n):
	m = 1
	for (b, i) in E[p]:
		if m == n:
			m += 1
		ans[i] = m
		sub(b, m)
		m += 1
sub(0, 0)
print(max(ans))
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N - 1):
	(a, b) = map(int, input().split())
	X[a - 1].append((i, b - 1))
Q = [(0, -1)]
ANS = [-1] * (N - 1)
maxc = 0
while Q:
	(x, c0) = Q.pop()
	c = 1
	for (i, y) in X[x]:
		if c == c0:
			c += 1
		ANS[i] = c
		if c > maxc:
			maxc = c
		Q.append((y, c))
		c += 1
print(maxc)
for ans in ANS:
	print(ans)


from collections import deque
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edges[a].append((b, i))
	edges[b].append((a, i))
ans = [0] * (n - 1)
q = deque()
next_v = edges[0]
for (c, (u, i)) in enumerate(next_v):
	q.append((u, i, c + 1))
	ans[i] = c + 1
while q:
	(up, _, cp) = q.popleft()
	next_v = edges[up]
	cnt = 1
	for (u, i) in next_v:
		if ans[i] > 0:
			continue
		if cnt == cp:
			cnt += 1
		ans[i] = cnt
		q.append((u, i, cnt))
		cnt += 1
print(max(ans))
for i in ans:
	print(i)


from collections import deque
n = int(input())
zyun = []
route = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	zyun.append([a, b])
	route[a].append(b)
iro = [0 for i in range(n + 1)]
ans = {}
q = deque()
q.append(1)
while q:
	now = q.popleft()
	cou = 1
	for k in route[now]:
		if iro[now] == cou:
			cou += 1
		ans[str(now) + '+' + str(k)] = cou
		iro[k] = cou
		q.append(k)
		cou += 1
print(max(iro))
for (i, j) in zyun:
	print(ans[str(i) + '+' + str(j)])


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
n = int(input())
edge = [[] for _ in [0] * n]
for i in range(~-n):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
	count = 1
	for (to, i) in edge[now]:
		if count == color:
			count += 1
		ans[i] = count
		dfs(to, count)
		count += 1
dfs(0, 0)
print(max(ans))
for p in ans:
	print(p)


import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
X = [deque() for _ in range(N)]
P = [-1] * N
for i in range(N - 1):
	(a, b) = map(int, input().split())
	X[a - 1].append((i, b - 1))
Q = deque([(0, -1)])
ANS = [-1] * (N - 1)
cmax = 0
while Q:
	(x, c0) = Q.pop()
	c = 1
	for (i, y) in X[x]:
		if c == c0:
			c += 1
		ANS[i] = c
		Q.appendleft((y, c))
		c += 1
	cmax = max(cmax, c - 1)
print(cmax)
for ans in ANS:
	print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
m = map(int, read().split())
AB = list(zip(m, m))
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)
color = [-1] * (N + 1)
for x in order:
	ng = color[x]
	c = 1
	for y in graph[x]:
		if y == parent[x]:
			continue
		if c == ng:
			c += 1
		color[y] = c
		c += 1
answer = []
for (a, b) in AB:
	if parent[a] == b:
		answer.append(color[a])
	else:
		answer.append(color[b])
K = max(answer)
print(K)
print('\n'.join(map(str, answer)))


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	t[a].append((b, i))
	t[b].append((a, i))

def dfs(v, p, pc):
	c = 1
	for (nv, edge) in t[v]:
		if nv == p:
			continue
		if c == pc:
			c += 1
		color[edge] = c
		dfs(nv, v, c)
		c += 1
dfs(0, -1, 0)
print(max(color))
print(*color, sep='\n')


from collections import defaultdict
N = int(input())
P = [[] for _ in range(N)]
AB = defaultdict(int)
for _ in range(N - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	P[a].append(b)
	P[b].append(a)
	AB[a, b] = -1
C = [-1] * N

def bfs(s):
	d = [-1] * N
	d[s] = 0
	p_old = [s]
	K = -1
	while p_old:
		p_new = []
		for i in p_old:
			c = 1
			for j in P[i]:
				if d[j] != -1:
					continue
				if C[i] == c:
					c += 1
				d[j] = 0
				p_new.append(j)
				C[j] = c
				AB[i, j] = c
				K = max(K, c)
				c += 1
		p_old = p_new
	return K
print(bfs(0))
for x in list(AB.values()):
	print(x)


from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append(b)
	color[a, b] = 0
for a in range(N):
	c_p = color_parents[a]
	c = 1
	for b in tree[a]:
		if c == c_p:
			c += 1
		color[a, b] = c
		color_parents[b] = c
		c += 1
print(max(color.values()))
for k in color.keys():
	print(color[k])


def main():
	import sys
	readline = sys.stdin.buffer.readline
	from collections import deque
	n = int(readline())
	ab = [list(map(int, readline().split())) for _ in range(n - 1)]
	l = [[] for _ in range(n + 1)]
	for (a, b) in ab:
		l[a].append(b)
		l[b].append(a)
	parents = [-1] * (n + 1)
	order = []
	q = deque()
	q.append(1)
	while q:
		c = q.pop()
		order.append(c)
		for i in l[c]:
			if i == parents[c]:
				continue
			parents[i] = c
			q.append(i)
	color = [-1] * (n + 1)
	for i in order:
		ng = color[i]
		c = 1
		for j in l[i]:
			if j == parents[i]:
				continue
			if c == ng:
				c += 1
			color[j] = c
			c += 1
	ans = []
	for (a, b) in ab:
		if a == parents[b]:
			ans.append(color[b])
		else:
			ans.append(color[a])
	print(max(ans))
	print('\n'.join(list(map(str, ans))))

def __starting_point():
	main()
__starting_point()


from collections import deque
n = int(input())
arr = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	arr[a - 1].append([b - 1, i])
	arr[b - 1].append([a - 1, i])
que = deque([0])
ans = [0] * (n - 1)
par = [0] * n
par[0] = -1
while que:
	x = que.popleft()
	p = par[x]
	color = 1
	for tup in arr[x]:
		if p == color:
			color += 1
		if ans[tup[1]] == 0:
			ans[tup[1]] = color
			par[tup[0]] = color
			color += 1
			que.append(tup[0])
print(max(ans))
print(*ans, sep='\n')


from collections import deque
N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append([b - 1, i])
	G[b - 1].append([a - 1, i])
q = deque()
q.append([0, 0, 0])
colors = [0] * (N - 1)
while q:
	(node, parent, edge_color) = q.popleft()
	c = 1
	for (child, index) in G[node]:
		if child == parent:
			continue
		if c == edge_color:
			c += 1
		q.append([child, node, c])
		colors[index] = c
		c += 1
print(max(colors))
print(*colors, sep='\n')


import collections
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append([b - 1, i])
	graph[b - 1].append([a - 1, i])
q = collections.deque()
ans = [-1] * (N - 1)
q.append([0, -1])
while len(q) != 0:
	tmp = 1
	(v, v2) = q.popleft()
	for (w, i) in graph[v]:
		if ans[i] != -1:
			continue
		if ans[v2] == tmp:
			tmp += 1
		ans[i] = tmp
		tmp += 1
		q.append([w, i])
print(len(set(ans)))
for i in ans:
	print(i)


from collections import deque
N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append([b, i])
	G[b].append([a, i])
ans = [0] * (N - 1)
q = deque([(0, -1)])
while q:
	(v, pc) = q.popleft()
	c = 1 if pc != 1 else 2
	for (nv, i) in G[v]:
		if ans[i] == 0:
			ans[i] = c
			q.append((nv, c))
			c += 1 if c + 1 != pc else 2
print(max(ans))
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append([b - 1, i])
colors = [-1] * (N - 1)

def func(a, p_color=-1):
	color = 1
	for (b, i) in edges[a]:
		if color == p_color:
			color += 1
		colors[i] = color
		func(b, color)
		color += 1
func(0, -1)
print(max(colors))
for c in colors:
	print(c)


from collections import deque

def main():
	n = int(input())
	adj = [[] for i in range(n + 1)]
	ab = [list(map(int, input().split())) for i in range(n - 1)]
	for (a, b) in ab:
		adj[a].append(b)
		adj[b].append(a)
	order = []
	parent = [0] * (n + 1)
	visited = [0] * (n + 1)
	visited[1] = 1
	q = deque([1])
	while q:
		par = q.popleft()
		order.append(par)
		for chl in adj[par]:
			if visited[chl]:
				continue
			visited[chl] = 1
			parent[chl] = par
			q.append(chl)
	cl = [None] * (n + 1)
	for par in order:
		pc = cl[par]
		color = 1
		for chl in adj[par]:
			if chl == parent[par]:
				continue
			if pc == color:
				color += 1
			cl[chl] = color
			color += 1
	g = max([len(i) for i in adj])
	print(g)
	for (a, b) in ab:
		if parent[a] != b:
			print(cl[b])
		else:
			print(cl[a])

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
V = [[] for _ in range(N)]
C = [-1 for _ in range(N - 1)]

def dfs(v, c, p):
	k = 1
	for (_v, _id) in V[v]:
		if _v == p:
			continue
		if k == c:
			k += 1
		C[_id] = k
		dfs(_v, k, v)
		k += 1
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	V[a].append([b, i])
	V[b].append([a, i])
dfs(0, -1, -1)
print(max(C))
for i in C:
	print(i)


N = int(input())
E = sorted([list(map(int, input().split())) + [i] for i in range(N - 1)], key=lambda x: x[1])
E.sort()
ans = [0 for _ in range(N - 1)]
flg = [0 for _ in range(N + 1)]
t = 0
cnt = 0
ans_a = 0
for i in range(N - 1):
	(a, b, ind) = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans[ind] = cnt
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1
print(ans_a)
for a in ans:
	print(a)


from collections import deque
n = int(input())
G = [[] for _ in range(n)]
L = []
ans = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	L.append(b - 1)
que = deque([0])
while que:
	s = que.pop()
	color = 1
	for ni in G[s]:
		if ans[s] == color:
			color += 1
		ans[ni] = color
		color += 1
		que.append(ni)
print(max(ans))
for i in L:
	print(ans[i])


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

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

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

class Graph:

	def __init__(self, v):
		from heapq import heappop, heappush
		self.v = v
		self.graph = [[] for _ in range(v)]
		self.INF = 10 ** 9

	def addEdge(self, start, end, itr):
		self.graph[start].append((end, itr))
		self.graph[end].append((start, itr))

	def BFS(self, start):
		from collections import deque
		dist = [-1] * self.v
		ret = [0] * (self.v - 1)
		que = deque()
		que.append((start, -1))
		dist[start] = 0
		while que:
			(now, _color) = que.popleft()
			color = 1
			if _color == color:
				color += 1
			for (to, itr) in self.graph[now]:
				if dist[to] == -1:
					que.append((to, color))
					dist[to] = dist[now] + 1
					ret[itr] = color
					color += 1
					if color == _color:
						color += 1
		return ret

	def color_types(self):
		ret = len(self.graph[0])
		for x in self.graph[1:]:
			ret = max(ret, len(x))
		return ret

def Main():
	n = read_int()
	g = Graph(n)
	for i in range(n - 1):
		(a, b) = read_ints()
		g.addEdge(~-a, ~-b, i)
	print(g.color_types())
	print(*g.BFS(0), sep='\n')

def __starting_point():
	Main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
ab = []
edge = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	ab.append((a, b))
	edge[a].append(b)
ans = {}

def solve(p, c):
	global ans
	cnt = 1
	for vtx in edge[p]:
		while c == cnt:
			cnt += 1
		ans[p, vtx] = cnt
		solve(vtx, cnt)
		cnt += 1
solve(0, 0)
print(max(ans.values()))
for e in ab:
	print(ans[e])


N = int(input())
import sys
sys.setrecursionlimit(4100000)
S = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	S[a - 1].append((b - 1, i))
	S[b - 1].append((a - 1, i))
L = [0] * (N - 1)

def dfs(node, pre_col, pre_node):
	col = 1
	for (next_node, i) in S[node]:
		if next_node == pre_node:
			continue
		if col == pre_col:
			col += 1
		L[i] = col
		dfs(next_node, col, node)
		col += 1
dfs(0, -1, -1)
print(max(L))
for l in L:
	print(l)


from sys import stdin

def getval():
	n = int(input())
	e = [[i] + list(map(int, stdin.readline().split())) for i in range(n - 1)]
	return (n, e)

def main(n, e):
	tree = [[] for i in range(n)]
	ans = [0 for i in range(n - 1)]
	for i in e:
		tree[i[1] - 1].append([i[2] - 1, i[0]])
	tree[0].append(0)
	k = 1
	q = [0]
	while q:
		n = 0
		idx = q.pop(0)
		for i in range(len(tree[idx]) - 1):
			n += 1
			if n == tree[idx][-1]:
				n += 1
			ans[tree[idx][i][-1]] = n
			tree[tree[idx][i][0]].append(n)
			q.append(tree[idx][i][0])
		k = max(k, n)
	print(k)
	for i in ans:
		print(i)

def __starting_point():
	(n, e) = getval()
	main(n, e)
__starting_point()


N = int(input())
G = [[] for n in range(N)]
vc = N * [0]
ec = (N - 1) * [0]
h = 1
for n in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append((b - 1, n))
for (v, g) in enumerate(G):
	t = 1
	for (b, i) in g:
		if vc[v] == t:
			t += 1
		vc[b] = t
		ec[i] = t
		h = max(h, t)
		t += 1
print(h)
for n in range(N - 1):
	print(ec[n])


import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
E = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a].append((b, i))
	E[b].append((a, i))
K = max((len(e) for e in E))
print(K)
ans = [-1] * (N - 1)

def dfs(v=1, p=0, p_col=-1):
	col = 1
	for (u, idx) in E[v]:
		if u == p:
			continue
		if col == p_col:
			col += 1
		ans[idx] = col
		dfs(u, v, col)
		col += 1
dfs()
print('\n'.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edge[a].append((b, 1 + i))
color = [0] * N

def dfs(v, c, idx):
	color[idx] = c
	now = 0
	for (nv, i) in edge[v]:
		now += 1
		if now == c:
			now += 1
		dfs(nv, now, i)
dfs(0, 0, 0)
color[0] = max(color)
print(*color, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
Graph = [[] for ii in range(N)]
for ii in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Graph[a].append([b, ii])
ans = [None] * (N - 1)

def rec(cur, color):
	cnt = 1
	for (to, jj) in Graph[cur]:
		if cnt == color:
			cnt += 1
		ans[jj] = cnt
		rec(to, cnt)
		cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(100000)
n = int(input())
g = [[] for _ in range(n)]
ans = [0] * (n - 1)

def dfs(v, c=-1, p=-1):
	k = 1
	for (u, ei) in g[v]:
		if u == p:
			continue
		if k == c:
			k += 1
		ans[ei] = k
		k += 1
		dfs(u, ans[ei], v)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append((b, i))
	g[b].append((a, i))
dfs(0)
mx = 0
for i in range(n):
	mx = max(mx, int(len(g[i])))
print(mx)
for i in ans:
	print(i)


n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
ans = [0] * (n - 1)
abi = [[] for _ in range(n + 1)]
import sys
sys.setrecursionlimit(4100000)
for (i, (a, b)) in enumerate(ab):
	abi[a].append((i, b))
	abi[b].append((i, a))

def dfs(v, parent=-1, color=-1):
	k = 1
	for i in abi[v]:
		if parent == i[1]:
			continue
		if k == color:
			k += 1
		ans[i[0]] = k
		k += 1
		dfs(i[1], v, ans[i[0]])
dfs(1)
print(max(ans))
for i in ans:
	print(i)


from collections import deque

def readinput():
	n = int(input())
	nList = []
	for _ in range(n + 1):
		nList.append([])
	edges = []
	for _ in range(n - 1):
		(a, b) = list(map(int, input().split()))
		edges.append((a, b))
		nList[a].append(b)
		nList[b].append(a)
	return (n, nList, edges)

def bfs(s, nList):
	WHITE = 0
	GRAY = 1
	BLACK = 2
	status = [WHITE] * (n + 1)
	parent = [0] * (n + 1)
	color = [0] * (n + 1)
	maxcolor = 0
	Q = deque([])
	Q.append(s)
	while len(Q) > 0:
		u = Q.popleft()
		usedcolor = color[u]
		col = 1
		for t in nList[u]:
			if status[t] == WHITE:
				status[t] = GRAY
				parent[t] = u
				if col == usedcolor:
					col += 1
				color[t] = col
				Q.append(t)
				col += 1
		maxcolor = max(maxcolor, col - 1)
		status[u] = BLACK
	return (color, maxcolor)

def main(n, nList, edges):
	(color, maxcolor) = bfs(1, nList)
	print(maxcolor)
	for (a, b) in edges:
		print(color[b])

def __starting_point():
	(n, nList, edges) = readinput()
	main(n, nList, edges)
__starting_point()


n = int(input())
X = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	X[a - 1].append([b - 1, i])
ANS = [0] * (n - 1)
VC = [0] * n
k = 1
for (v, c) in enumerate(X):
	t = 1
	for (b, i) in c:
		if VC[v] == t:
			t += 1
		VC[b] = t
		ANS[i] = t
		k = max(k, t)
		t += 1
print(k)
for i in range(n - 1):
	print(ANS[i])


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
ki = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ki[a].append([b, i])
ans = [-1] * (n - 1)

def d(index, color):
	cnt = 1
	for (t, jid) in ki[index]:
		if cnt == color:
			cnt += 1
		ans[jid] = cnt
		d(t, cnt)
		cnt += 1
d(0, 0)
print(max(ans))
for i in ans:
	print(i)


n = int(input())
A = []
g = [[] for _ in range(n + 1)]
ans = {}
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	A.append([a, b])
from collections import deque
q = deque()
q.append(1)
color = [-1] * (n + 1)
color[1] = 0
cnt = 0
while q:
	v = q.popleft()
	p = 1
	for u in g[v]:
		if p == color[v]:
			p += 1
		color[u] = p
		ans[v, u] = p
		q.append(u)
		cnt = max(cnt, p)
		p += 1
print(cnt)
for i in range(n - 1):
	tmp = (A[i][0], A[i][1])
	print(ans[tmp])


n = int(input())
import sys
sys.setrecursionlimit(10 ** 6)
s = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	s[a - 1].append((b - 1, i))
	s[b - 1].append((a - 1, i))
l = [0] * (n - 1)

def dfs(node, pre_col, par):
	col = 1
	for (nei, i) in s[node]:
		if nei == par:
			continue
		if col == pre_col:
			col += 1
		l[i] = col
		dfs(nei, col, node)
		col += 1
dfs(0, -1, -1)
print(max(l))
for i in l:
	print(i)


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
sortedAB = sorted(AB)
con = {i: [] for i in range(1, N + 1)}
color = [0] * (N + 1)
for (a, b) in sortedAB:
	con[a].append(b)
for i in range(1, N + 1):
	now_c = 1
	for c in con[i]:
		if color[i] == now_c:
			now_c += 1
		color[c] = now_c
		now_c += 1
print(max(color))
for i in range(N - 1):
	print(color[AB[i][1]])
a = 0


from collections import deque
N = int(input())
G = [{} for i in range(N + 1)]
colors = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a][b] = [i, -1]
	G[b][a] = [i, -1]

def bfs(s):
	seen = [0 for i in range(N + 1)]
	prev = [0 for i in range(N + 1)]
	todo = deque([])
	cmax = 0
	now = s
	seen[now] = 1
	todo.append(now)
	while 1:
		if len(todo) == 0:
			break
		a = todo.popleft()
		if len(G[a]) < 50:
			if prev[a] == 0:
				a_color = set([])
			else:
				a_color = set([G[a][prev[a]][1]])
			for b in G[a]:
				if seen[b] == 0:
					seen[b] = 1
					todo.append(b)
					prev[b] = a
					for c in range(1, N + 1):
						if c not in a_color:
							a_color.add(c)
							colors.append((G[a][b][0], c))
							G[a][b][1] = G[b][a][1] = c
							if c > cmax:
								cmax = c
							break
		else:
			temp = list(range(1, N))
			if prev[a] != 0:
				del temp[G[a][prev[a]][1] - 1]
			temp = deque(temp)
			for (i, b) in enumerate(G[a]):
				if seen[b] == 0:
					seen[b] = 1
					todo.append(b)
					prev[b] = a
					c = temp.popleft()
					colors.append((G[a][b][0], c))
					G[a][b][1] = G[b][a][1] = c
					if c > cmax:
						cmax = c
	return (colors, cmax)
(colors, cmax) = bfs(1)
colors = sorted(colors)
print(cmax)
for i in range(N - 1):
	print(colors[i][1])


from collections import deque
N = int(input())
tree = [[] for i in range(N)]
key_order = [0] * (N - 1)
for i in range(N - 1):
	(in1, in2) = map(int, input().split())
	in1 -= 1
	in2 -= 1
	tree[in1].append(in2)
	tree[in2].append(in1)
	key_order[i] = (in1, in2)

def bfs(tree, p):
	seen = [False] * len(tree)
	queue = deque((p,))
	edge_colors = dict()
	node_colors = [0] * len(tree)
	while len(queue) > 0:
		q = queue.popleft()
		seen[q] = True
		parent_color = node_colors[q]
		cnt = 1
		for v in tree[q]:
			if not seen[v]:
				if cnt == parent_color:
					cnt += 1
				edge_colors[q, v] = cnt
				node_colors[v] = cnt
				queue.append(v)
				cnt += 1
	return edge_colors
edge_colors = bfs(tree, 0)
print(max([c for (key, c) in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
N = INT()
ab = [LIST() for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (a, b) in ab:
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
length = [len(x) for x in graph]
ans = max(length)
color = defaultdict(int)
q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1
while q:
	(n, previous, col) = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[n, x] = col
			color[x, n] = col
		else:
			if cnt == col:
				cnt += 1
			color[n, x] = cnt
			color[x, n] = cnt
			q.append((x, n, cnt))
			cnt += 1
print(ans)
for (a, b) in ab:
	print(color[a - 1, b - 1])


import sys
from collections import deque
read = sys.stdin.read
(N, *ab) = map(int, read().split())
graph = [[] for _ in range(N + 1)]
for (a, b) in zip(*[iter(ab)] * 2):
	graph[a].append(b)
color = [0] * (N + 1)
queue = deque([1])
while queue:
	V = queue.popleft()
	number = 1
	for v in graph[V]:
		if number == color[V]:
			number += 1
		color[v] = number
		queue.append(v)
		number += 1
print(max(color))
for (a, b) in zip(*[iter(ab)] * 2):
	print(color[b])


from collections import defaultdict, deque, Counter
N = int(input())
counter = Counter()
nodes = defaultdict(list)
edges = []
for i in range(N - 1):
	(u, v) = list(map(int, input().split(' ')))
	nodes[u].append((v, i))
	nodes[v].append((u, i))
	edges.append((u, v))
K = 0
for node in list(nodes.values()):
	K = max(K, len(node))
checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N
while queue:
	(u, uc) = queue.popleft()
	checked.add(u)
	color = 1
	for (v, e) in nodes[u]:
		if v in checked:
			continue
		if color == uc:
			color += 1
		edge_colors[e] = color
		queue.append((v, color))
		color += 1
print(K)
for i in range(N - 1):
	print(edge_colors[i])


from collections import deque
N = int(input())
P = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	P[a - 1].append((b - 1, i))
(q, ans) = (deque(), [0] * (N - 1))
q.append((0, 0))
while len(q) > 0:
	((c, n), ac) = (q.popleft(), 1)
	for (l, i) in P[n]:
		if ac == c:
			ac += 1
		q.append((ac, l))
		ans[i] = ac
		ac += 1
print(max(ans))
for a in ans:
	print(a)


from collections import defaultdict, deque
graph = defaultdict(list)
(N, *AB) = map(int, open(0).read().split())
for (a, b) in zip(*[iter(AB)] * 2):
	graph[a].append(b)
stack = deque([1])
C = [0] * (N + 1)
while stack:
	v = stack.popleft()
	c = 0
	for w in graph[v]:
		c += 1 + (c + 1 == C[v])
		C[w] = c
		stack.append(w)
print(max(C))
print('\n'.join((str(C[b]) for b in AB[1::2])))


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
G = [[] for _ in range(n)]
E = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
	E.append((a, b))
cs = []
ans = {}

def dfs(v, p, c):
	color = 0
	for g in G[v]:
		if g == p:
			continue
		color += 1
		if color == c:
			color += 1
		dfs(g, v, color)
		ans[v + 1, g + 1] = color
dfs(0, -1, 0)
print(max(ans.values()))
for e in E:
	print(ans[e])


import sys
from collections import deque
N = int(input())
E = [tuple(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for _ in range(N - 1)]
G = [[] for _ in range(N)]
for (a, b) in E:
	G[a].append(b)
colornum = len(G[0])
colors = [{} for _ in range(N)]
todo = deque()
for (i, p) in enumerate(G[0]):
	colors[0][p] = i
	todo.append((0, p))
while todo:
	(pp, p) = todo.popleft()
	colornum = max(colornum, len(G[p]) + 1)
	c = colors[pp][p]
	for np in G[p]:
		c = (c + 1) % colornum
		colors[p][np] = c
		todo.append((p, np))
print(colornum)
for (a, b) in E:
	print(colors[a][b] + 1)


import sys
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(1, N)]
co = [0 for _ in range(N)]
prev = 0
color = 1
for (a, b) in sorted(AB):
	if prev != a:
		color = 1
	if co[a - 1] == color:
		color += 1
	co[b - 1] = color
	prev = a
	color += 1
print(max(co))
for (_, b) in AB:
	print(co[b - 1])


import sys
sys.setrecursionlimit(500000)
N = int(input())
G = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append((b, i))
	G[b].append((a, i))
color = max((len(g) for g in G))
print(color)
ans = [-1] * (N - 1)

def dfs(v=1, p=0, p_col=-1):
	col = 1
	for (side, idx) in G[v]:
		if side != p:
			if col == p_col:
				col += 1
			ans[idx] = col
			dfs(side, v, col)
			col += 1
dfs()
print('\n'.join(map(str, ans)))


from collections import deque
n = int(input())
g = [[] for i in range(n + 1)]
clst = [-1] * (n - 1)
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	g[a].append([b, i])
	g[b].append([a, i])
q = deque([[1, 0]])
k = 0
while len(q) > 0:
	(u, c) = deque.popleft(q)
	clr = 1
	for (v, i) in g[u]:
		if clst[i] == c:
			continue
		if clr == c:
			clr += 1
		clst[i] = clr
		deque.append(q, [v, clr])
		clr += 1
	k = max(k, clr - 1)
print(k)
for i in range(n - 1):
	print(clst[i])


import sys
sys.setrecursionlimit(1000000)
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, i])
	g[b - 1].append([a - 1, i])
ans = [0 for i in range(N - 1)]

def dfs(i, j, col):
	k = 1
	for nec in g[i]:
		if nec[0] == j:
			continue
		if k == col:
			k += 1
		ans[nec[1]] = k
		dfs(nec[0], i, k)
		k += 1
dfs(0, -1, -1)
print(max(ans))
for i in range(N - 1):
	print(ans[i])


n = int(input())
ne = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	ne[a].append((i + 1, b))
	ne[b].append((i + 1, a))
maxp = 0
ce = [0] * n
cr = [0] * (n + 1)
for i in range(1, n + 1):
	ptr = 1
	while len(ne[i]) != 0:
		if ptr == cr[i]:
			ptr += 1
			continue
		else:
			(cur, root) = ne[i].pop()
			if ce[cur] == 0:
				ce[cur] = ptr
				cr[root] = ptr
				if ptr > maxp:
					maxp = ptr
				ptr += 1
print(maxp)
for i in range(1, n):
	print(ce[i])


from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n - 1):
	(b, c) = map(int, input().split())
	b -= 1
	c -= 1
	a[b].append(c)
	e.append(c)
col = [0 for i in range(n)]
v = deque([0])
while v:
	d = v.popleft()
	k = 1
	for i in a[d]:
		if col[d] == k:
			k += 1
		col[i] = k
		v.append(i)
		k += 1
print(max(col))
for i in e:
	print(col[i])


import sys
sys.setrecursionlimit(10 ** 8)

def dfs(x, last=-1, ban_color=-1):
	color = 1
	for to in vertex[x]:
		if to == last:
			continue
		if color == ban_color:
			color += 1
		color_dic[x, to] = color
		dfs(to, x, color)
		color += 1
n = int(input())
vertex = {i: [] for i in range(n)}
a = [0] * (n - 1)
b = [0] * (n - 1)
color_dic = {}
for i in range(n - 1):
	(a[i], b[i]) = list(map(int, input().split()))
	a[i] -= 1
	b[i] -= 1
	vertex[a[i]].append(b[i])
	vertex[b[i]].append(a[i])
max_v = 0
for (_, v) in list(vertex.items()):
	if len(v) > max_v:
		max_v = len(v)
print(max_v)
dfs(0)
for i in range(n - 1):
	if (a[i], b[i]) in color_dic:
		print(color_dic[a[i], b[i]])
	else:
		print(color_dic[b[i], a[i]])


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	e.append(b - 1)
stack = deque([0])
stack.append(0)
ans = [0 for _ in range(n)]
while stack:
	v = stack.popleft()
	c = 1
	for nv in g[v]:
		if ans[v] == c:
			c += 1
		ans[nv] = c
		c += 1
		stack.append(nv)
print(max(ans))
for i in e:
	print(ans[i])


import sys
sys.setrecursionlimit(10 ** 5)
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
graph = [[] for _ in range(n + 1)]
ans = [0] * (n - 1)
for i in range(n - 1):
	graph[ab[i][0]].append((ab[i][1], i))
	graph[ab[i][1]].append((ab[i][0], i))
visit = [False] * (n + 1)

def dfs(p, c):
	color = 1
	visit[p] = True
	for (n, i) in graph[p]:
		if visit[n] == False:
			if color == c:
				color += 1
			ans[i] = color
			dfs(n, color)
			color += 1
dfs(1, 0)
print(max(ans))
for t in ans:
	print(t)


n = int(input())
G = [[] for _ in range(n)]
edge = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	edge.append(b)
from collections import deque
q = deque()
color = [0] * n
q.append(0)
while q:
	cur = q.popleft()
	c = 1
	for nx in G[cur]:
		if color[cur] == c:
			c += 1
		color[nx] = c
		c += 1
		q.append(nx)
print(max(color))
for e in edge:
	print(color[e])


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append((b - 1, i))
	edges[b - 1].append((a - 1, i))

def dfs(v, c=-1, p=-1):
	k = 1
	for (nv, ei) in edges[v]:
		if nv == p:
			continue
		if k == c:
			k += 1
		ans[ei] = k
		k += 1
		dfs(nv, ans[ei], v)
ans = [None] * (n - 1)
dfs(0)
print(max(ans))
for i in ans:
	print(i)


import sys
from collections import deque, defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
graph = [[] for _ in range(N + 1)]
AB = []
for i in range(N - 1):
	(a, b) = map(int, readline().split())
	AB.append((a, b))
	graph[a].append(b)
	graph[b].append(a)
dist = [-1] * (N + 1)
dist[1] = 0
COL = defaultdict()
q = deque([(1, 0)])
max_col = 0

def bfs(max_col):
	while q:
		(x, pre_col) = q.popleft()
		c = 1
		for nx in graph[x]:
			if dist[nx] != -1:
				continue
			if c == pre_col:
				c += 1
			COL[x, nx] = c
			dist[nx] = 1
			q.append((nx, c))
			max_col = max(max_col, c)
			c += 1
	return max_col
max_col = bfs(max_col)
print(max_col)
for (a, b) in AB:
	if (a, b) in COL:
		print(COL[a, b])
	else:
		print(COL[b, a])


from collections import deque, defaultdict
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
d = [0] * (N + 1)
G = [[] for _ in range(N + 1)]
for (a, b) in ab:
	d[a] += 1
	d[b] += 1
	G[a].append(b)
	G[b].append(a)
print(max(d))
color = defaultdict(int)
q = deque([[1, 0]])
seen = [0] * (N + 1)
while q:
	(v, c) = q.popleft()
	seen[v] = 1
	tem = 1
	for u in G[v]:
		if seen[u]:
			continue
		if tem == c:
			tem += 1
		q.append([u, tem])
		(i, j) = (min(v, u), max(v, u))
		color[i, j] = tem
		tem += 1
for (a, b) in ab:
	(i, j) = (min(a, b), max(a, b))
	print(color[i, j])


from collections import deque
N = int(input())
dic = {i: [] for i in range(1, N + 1)}
rlt = [0] * (N - 1)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	dic[a].append((b, i))
	dic[b].append((a, i))
h = deque([(1, 1)])
while h:
	j = 1
	c = 0
	t = h.popleft()
	for k in dic[t[0]]:
		if k[0] == t[1]:
			c = rlt[k[1]]
			break
	for k in dic[t[0]]:
		if k[0] == t[1]:
			continue
		if c == j:
			j += 1
		rlt[k[1]] = j
		h.append((k[0], t[0]))
		j += 1
print(max(rlt))
for l in rlt:
	print(l)


from collections import deque
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
l = [[] for _ in range(n + 1)]
for (a, b) in ab:
	l[a].append(b)
	l[b].append(a)
parents = [-1] * (n + 1)
order = []
q = deque()
q.append(1)
while q:
	c = q.pop()
	order.append(c)
	for i in l[c]:
		if i == parents[c]:
			continue
		parents[i] = c
		q.append(i)
color = [-1] * (n + 1)
for i in order:
	ng = color[i]
	c = 1
	for j in l[i]:
		if j == parents[i]:
			continue
		if c == ng:
			c += 1
		color[j] = c
		c += 1
ans = []
for (a, b) in ab:
	if a == parents[b]:
		ans.append(color[b])
	else:
		ans.append(color[a])
print(max(ans))
print('\n'.join(list(map(str, ans))))


import sys
input = sys.stdin.readline
n = int(input())
edges = []
for id in range(n - 1):
	(a, b) = map(int, input().split())
	edges.append([a - 1, b - 1, id])
edges.sort()
used = [0] * n
ans = [0] * (n - 1)
num = 1
prev = 0
for edge in edges:
	(_from, to, id) = edge
	if _from != prev:
		num = 1
	if used[_from] == num:
		num += 1
	ans[id] = num
	used[to] = num
	num += 1
	prev = _from
print(max(ans))
for color in ans:
	print(color)


N = int(input())
num = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	num[a - 1].append([i, b - 1])
answer = [0] * (N - 1)
color = [-1] * N
max_num = 0
for i in range(len(num)):
	if max_num <= len(num[i]):
		if i == 0:
			max_num = len(num[i])
		else:
			max_num = len(num[i]) + 1
	c = 1
	for j in range(len(num[i])):
		if c == color[i]:
			c += 1
		answer[num[i][j][0]] = c
		color[num[i][j][1]] = c
		c += 1
print(max_num)
for i in answer:
	print(i)


def __starting_point():
	import sys
	from collections import deque
	input = sys.stdin.readline
	N = int(input())
	edges = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		edges[a].append((b, i))
		edges[b].append((a, i))
	color = [None] * (N - 1)
	SIZE = 1
	q = deque([(0, None)])
	while q:
		(v, prev_color) = q.popleft()
		c = 1
		for (w, i) in edges[v]:
			if not color[i]:
				if c == prev_color:
					c += 1
				color[i] = c
				c += 1
				q.append((w, color[i]))
		SIZE = max(SIZE, c - 1)
	print(SIZE)
	for n in range(N - 1):
		print(color[n])
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1] += [(b - 1, i)]
	g[b - 1] += [(a - 1, i)]
l = [0] * (n - 1)

def dfs(v, p=-1, s=-1):
	t = 1
	for (c, i) in g[v]:
		if c == p:
			continue
		if t == s:
			t += 1
		l[i] = t
		dfs(c, v, t)
		t += 1
dfs(0)
print(max(l))
for i in l:
	print(i)


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, i))
v_color = [0] * N
e_color = [0] * (N - 1)
K = 1
for (a, children) in enumerate(G):
	c = 1
	for (b, i) in children:
		if c == v_color[a]:
			c += 1
		v_color[b] = c
		e_color[i] = c
		K = max(K, c)
		c += 1
print(K)
print('\n'.join(map(str, e_color)))


import sys
input = sys.stdin.readline
n = int(input())
l = [[]]
nn = []
for _ in range(n + 1):
	l.append([])
for i in range(n - 1):
	(a, b) = map(int, input().split())
	l[a].append(b)
	l[b].append(a)
	nn.append(b)
ml = list(map(len, l))
m = max(ml)
co = []
for i in range(n + 1):
	co.append(set(range(1, ml[i] + 1)))
col = [0] * (n + 1)
col[1] = 1
for i in range(1, n + 1):
	for la in l[i]:
		if col[la] == 0:
			col[la] = co[i].pop()
			co[la].discard(col[la])
print(m)
for i in range(n - 1):
	print(col[nn[i]])


from collections import deque

def main():
	N = int(input())
	Node = [set() for _ in range(N)]
	Edge = {}
	for i in range(N - 1):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		if b < a:
			(a, b) = (b, a)
		Edge[a, b] = i
		Node[a].add(b)
		Node[b].add(a)
	K = 0
	for (i, x) in enumerate(Node):
		if len(x) > K:
			K = len(x)
			top = i
	q = deque()
	seen = [False] * (N - 1)
	used = [set() for _ in range(N)]
	q.append(top)
	while len(q) > 0:
		cur = q.popleft()
		col = 1
		for i in Node[cur]:
			if cur > i:
				ed = (i, cur)
			else:
				ed = (cur, i)
			if seen[Edge[ed]] == False:
				while col in used[cur] or col in used[i]:
					col += 1
				seen[Edge[ed]] = col
				used[cur].add(col)
				used[i].add(col)
				q.append(i)
	print(K)
	print('\n'.join(map(str, seen)))

def __starting_point():
	main()
__starting_point()


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
n = int(input())
edge = [tuple((int(i) for i in input().split())) for i in range(n - 1)]
to = [[] for _ in range(n + 1)]
for e in edge:
	(a, b) = e
	to[a].append(b)
	to[b].append(a)
color = {}

def f(cn, pn, pc):
	c = 1
	for nn in to[cn]:
		if nn == pn:
			continue
		if c == pc:
			c += 1
		tmp = (cn, nn)
		color[min(tmp), max(tmp)] = c
		f(nn, cn, c)
		c += 1
f(1, 0, 0)
print(max(color.values()))
for key in edge:
	print(color[key])


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
adj = defaultdict(list)
for (i, (a, b)) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))
k = max([len(li) for li in adj.values()])
print(k)
ans = [-1] * (n - 1)

def dfs(u, p_col):
	col = 1
	for (v, i) in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1
dfs(0, -1)
print(*ans, sep='\n')


from collections import deque
n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
print(max(ans))
for node in node_list:
	print(ans[node])


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, sys.stdin.readline().split())
	g[a - 1].append([b - 1, i])
	g[b - 1].append([a - 1, i])
print(max((len(v) for v in g)))
l = [0] * (n - 1)

def dfs(v, p=-1, c=-1):
	k = 1
	for (u, e) in g[v]:
		if u == p:
			continue
		if k == c:
			k += 1
		l[e] = k
		dfs(u, v, k)
		k += 1
dfs(0)
for c in l:
	print(c)


import sys
input = sys.stdin.readline
N = int(input())
q = []
l = [[] for i in range(N)]
ans = [1] * N
ans[0] = 0
for i in range(N - 1):
	(a, b) = map(int, input().split())
	q.append([a - 1, b - 1])
	l[a - 1].append(b - 1)
mx = 0
for (index, item) in enumerate(l):
	color = 1
	while item:
		temp = item.pop(-1)
		if color == ans[index]:
			color += 1
		ans[temp] = color
		color += 1
	mx = max(color - 1, mx)
print(mx)
for (_, item) in q:
	print(ans[item])


import sys
sys.setrecursionlimit(10000000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
path = [list() for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = (ab[i][0], ab[i][1])
	path[a].append([b, i])
	path[b].append([a, i])
color_max = 0
color_list = [0] * (N - 1)
visit = [False] * (N + 1)
visit[1] = True

def dfs(node, color, used_path):
	nonlocal visit
	nxt_color = 0
	for nxt in path[node]:
		nxt_node = nxt[0]
		use_path = nxt[1]
		if visit[nxt_node] == False:
			visit[nxt_node] = True
			nxt_color += 1
			if nxt_color == color:
				nxt_color += 1
			dfs(nxt_node, nxt_color, use_path)
	nonlocal color_list
	if used_path != -1:
		color_list[used_path] = color
dfs(1, 0, -1)
for c in color_list:
	color_max = max(c, color_max)
print(color_max)
print('\n'.join(map(str, color_list)))


N = int(input())
edge = {}
tree = [[] for i in range(N)]
colors = [1] * (N - 1)
c_p = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	tree[a].append(b)
	edge[a, b] = i
for i in range(N):
	c = 1
	for v_c in tree[i]:
		while c in c_p[i]:
			c += 1
		colors[edge[i, v_c]] = c
		c_p[v_c].append(c)
		c += 1
print(max(colors))
print(*colors, sep='\n')


N = int(input())
A = [[] for _ in range(N - 1)]
B = [0] * N
C = [0] * N
D = [0] * N
for i in range(N - 1):
	(a, b) = map(int, input().split())
	A[a - 1].append(b)
	C[b - 1] = i + 1
for i in range(N - 1):
	c = 0
	for j in A[i]:
		while True:
			c += 1
			if c != B[i]:
				B[j - 1] = c
				break
print(max(B))
for i in range(1, N):
	D[C[i]] = B[i]
for i in range(1, N):
	print(D[i])


import sys
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, sys.stdin.readline().split())
	g[a - 1].append([b - 1, i])
	g[b - 1].append([a - 1, i])
print(max((len(v) for v in g)))
from collections import deque
l = [0] * (n - 1)
q = deque([0])
b = [1] + [0] * (n - 1)
while q:
	v = q.pop()
	c = -1
	k = 1
	for (u, e) in g[v]:
		if b[u]:
			c = l[e]
	for (u, e) in g[v]:
		if b[u]:
			continue
		if k == c:
			k += 1
		l[e] = k
		k += 1
		q.appendleft(u)
		b[u] = 1
for c in l:
	print(c)


n = int(input())
l = [list(map(int, input().split())) + [i + 1] for i in range(n - 1)]
l.sort()
flg = [0 for _ in range(n + 1)]
ans = [0 for _ in range(n)]
t = 0
count = 0
for i in range(n - 1):
	(a, b, c) = l[i]
	if t != a:
		t = a
		count = 1
	if flg[a] == count:
		count += 1
	flg[b] = count
	ans[c] = count
	count += 1
print(max(flg))
for i in range(1, n):
	print(ans[i])


N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N - 1):
	(a, b) = map(int, input().split())
	X[a - 1].append((i, b - 1))
	P[b - 1] = a - 1
Q = [(0, -1)]
ANS = [-1] * (N - 1)
while Q:
	(x, c0) = Q.pop()
	c = 1
	for (i, y) in X[x]:
		if c == c0:
			c += 1
		ANS[i] = c
		Q.append((y, c))
		c += 1
print(max(ANS))
for ans in ANS:
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
graph = [[] for _ in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append([b, i])

def dfs(now, color):
	cnt = 1
	for (to, num) in graph[now]:
		if cnt == color:
			cnt += 1
		ans[num] = cnt
		dfs(to, cnt)
		cnt += 1
dfs(0, 0)
print(max(ans))
for i in ans:
	print(i)


import sys
sys.setrecursionlimit(100000)

def main():
	n = int(input())
	G = [[] for _ in range(n)]
	ID = [dict() for _ in range(n)]
	for i in range(n - 1):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		G[a].append(b)
		G[b].append(a)
		ID[a][b] = i
		ID[b][a] = i
	m = max((len(g) for g in G))
	ans = [0] * (n - 1)

	def bfs(a, pre=-1, pre_c=-1):
		color = 1
		for b in G[a]:
			if b == pre:
				continue
			if color == pre_c:
				color += 1
			ans[ID[a][b]] = color
			bfs(b, a, color)
			color += 1
	bfs(0)
	print(m)
	[print(a) for a in ans]

def __starting_point():
	main()
__starting_point()


from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
ends = []
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edges[a].append(b)
	ends.append(b)
nodes = deque([1])
count = [0] * (N + 1)
while nodes:
	node = nodes.popleft()
	nodes.extend(edges[node])
	c = 0
	for n in edges[node]:
		c += 1 + (c + 1 == count[node])
		count[n] = c
print(max(count))
for i in ends:
	print(count[i])


import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a].append((b, i))
	E[b].append((a, i))
K = max((len(e) for e in E))
print(K)
Ans = [-1] * (N - 1)

def dfs(v, pc=-1, p=-1):
	c = 1
	for (u, idx) in E[v]:
		if u == p:
			continue
		if c == pc:
			c += 1
		Ans[idx] = c
		dfs(u, c, v)
		c += 1
dfs(1)
print('\n'.join(map(str, Ans)))


import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter

def input():
	return sys.stdin.readline().strip()

def mp():
	return list(map(int, input().split()))

def lmp():
	return list(map(int, input().split()))
n = int(input())
edge = [[] for i in range(n + 1)]
par = [0] * (n + 1)
par[1] = -1
col = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = mp()
	edge[a].append([a, b, i])
	edge[b].append([b, a, i])
que = deque([edge[1]])
while len(que):
	k = 1
	q = que.popleft()
	for (x, y, i) in q:
		if col[i] == 0:
			if k == par[x]:
				k += 1
			col[i] = k
			par[y] = k
			k += 1
			que.append(edge[y])
print(max(col))
for i in range(n - 1):
	print(col[i])


from collections import deque
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
lines = [[] for _ in range(N + 1)]
for (a, b) in ab:
	lines[a].append(b)
q = deque([1])
color = [0] * (N + 1)
while q:
	x = q.popleft()
	c = 1
	for y in lines[x]:
		if c == color[x]:
			c += 1
		color[y] = c
		c += 1
		q.append(y)
print(max(color))
for i in range(N - 1):
	print(color[ab[i][1]])


N = int(input())
data = [0] * (N - 1)
cho = [0] * (N + 1)
res = [0] * (N - 1)
for i in range(0, N - 1):
	di = list(map(int, input().split()))
	di.append(i)
	data[i] = di
data = sorted(data)
for i in range(0, N - 1):
	if i != 0 and data[i][0] == data[i - 1][0]:
		cur += 1
	else:
		cur = 1
	if cur == cho[data[i][0]]:
		cur += 1
	res[data[i][2]] = cur
	cho[data[i][1]] = cur
print(max(cho))
for item in res:
	print(item)


INT = lambda : int(input())
INTM = lambda : map(int, input().split())
STRM = lambda : map(str, input().split())
STR = lambda : str(input())
LIST = lambda : list(map(int, input().split()))
LISTS = lambda : list(map(str, input().split()))
from collections import deque

class Graph:

	def __init__(self, v):
		from heapq import heappop, heappush
		self.v = v
		self.graph = [[] for _ in range(v)]
		self.INF = 10 ** 9

	def addEdge(self, start, end, edge):
		self.graph[start].append((end, edge))
		self.graph[end].append((start, edge))

def do():
	n = INT()
	g = Graph(n)
	for i in range(n - 1):
		(a, b) = INTM()
		a -= 1
		b -= 1
		g.addEdge(a, b, i)
	que = deque()
	check = [True] * n
	clrs = [0] * (n - 1)
	que.append([0, 0])
	check[0] = False
	while que:
		clr = 1
		(now, clr_f) = que.popleft()
		if clr_f == 1:
			clr = 2
		for (next, i) in g.graph[now]:
			if check[next]:
				check[next] = False
				que.append([next, clr])
				clrs[i] = clr
				clr += 1
				if clr == clr_f:
					clr += 1
	print(max(clrs))
	for i in range(n - 1):
		print(clrs[i])

def __starting_point():
	do()
__starting_point()


def p_d():
	n = int(input())
	t = [[] for _ in range(n)]
	p = [-1] * n
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		t[a - 1].append((i, b - 1))
		p[b - 1] = a - 1
	q = [(0, -1)]
	ans = [-1] * (n - 1)
	while q:
		(x, c0) = q.pop()
		c = 1
		for (i, y) in t[x]:
			if c == c0:
				c += 1
			ans[i] = c
			q.append((y, c))
			c += 1
	print(max(ans))
	for a in ans:
		print(a)
p_d()


import sys
sys.setrecursionlimit(500000)
n = int(input())
l = [[] for i in range(n)]
ans = [0] * (n - 1)

def dfs(v, c, p):
	k = 1
	for i in range(len(l[v])):
		u = l[v][i][0]
		id = l[v][i][1]
		if u == p:
			continue
		if k == c:
			k += 1
		ans[id] = k
		dfs(u, ans[id], v)
		k += 1
for i in range(n - 1):
	(a, b) = map(int, input().split())
	l[a - 1].append((b - 1, i))
	l[b - 1].append((a - 1, i))
dfs(0, -1, -1)
print(max(ans))
for i in ans:
	print(i)


from collections import deque
n = int(input())
g = [[] for _ in range(n + 1)]
e = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	e.append(b - 1)
q = deque([0])
color = [0 for _ in range(n)]
while len(q) > 0:
	ei = q.popleft()
	c = 1
	for x in g[ei]:
		if c == color[ei]:
			c += 1
		color[x] = c
		c += 1
		q.append(x)
print(max(color))
for i in e:
	print(color[i])


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
tree = [[] for _ in range(N)]
ans = [-1] * (N - 1)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a - 1].append((b - 1, i))
	tree[b - 1].append((a - 1, i))

def dfs(now, prev=-1, color=0):
	color_num = 1
	for (i, j) in tree[now]:
		if i == prev:
			continue
		if color_num == color:
			color_num = color_num + 1
		ans[j] = color_num
		dfs(i, now, color_num)
		color_num = color_num + 1
dfs(0)
print(max(ans))
for i in range(N - 1):
	print(ans[i])


import sys
sys.setrecursionlimit(10 ** 9)
data = int(input())
array = [[] for i in range(data)]
for i in range(data - 1):
	(a, b) = map(int, input().split())
	array[a - 1].append([b - 1, i])
result = [None] * (data - 1)

def func(prt, col):
	cnt = 1
	for (cld, org) in array[prt]:
		if cnt == col:
			cnt += 1
		result[org] = cnt
		func(cld, cnt)
		cnt += 1
func(0, 0)
print(max(result))
for i in range(data - 1):
	print(result[i])


from collections import deque
(N, *AB) = map(int, open(0).read().split())
E = [set() for _ in range(N + 1)]
for (i, (a, b)) in enumerate(zip(*[iter(AB)] * 2)):
	E[a].add((b, i))
	E[b].add((a, i))
A = [0] * (N - 1)
Q = deque([(0, 1)])
while Q:
	(p, v) = Q.popleft()
	c = 0
	for (u, i) in E[v]:
		E[u].remove((v, i))
		c += 1 + (c + 1 == p)
		Q.append((c, u))
		A[i] = c
print(max(A), *A)


import sys
from collections import defaultdict, deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
N = int(readline())
g = [[] for _ in range(N)]
deg = [0] * N
ab = defaultdict(int)
for _ in range(N - 1):
	(a, b) = list(map(int1, readline().split()))
	g[a].append(b)
	g[b].append(a)
	deg[a] += 1
	deg[b] += 1
	ab[a, b] = -1
color = [-1] * N
print(max(deg))
C = [0] * N
C[0] = -1
que = deque([0])
while len(que) != 0:
	idx = que.popleft()
	tmp = 1
	for i in g[idx]:
		if C[i] != 0:
			continue
		(a, b) = (idx, i)
		if tmp == C[idx]:
			tmp += 1
		ab[a, b] = tmp
		C[i] = tmp
		que.append(i)
		tmp += 1
for v in list(ab.values()):
	print(v)


n = int(input())
a = [set() for i in range(n)]
e = []
for i in range(n - 1):
	(b, c) = map(int, input().split())
	b -= 1
	c -= 1
	a[b].add(c)
	a[c].add(b)
	e.append(c)
col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [0]
while v:
	d = v.pop(0)
	k = 1
	for i in a[d]:
		if visited[i] == False:
			if col[d] == k:
				k += 1
			col[i] = k
			visited[i] = True
			v.append(i)
			k += 1
print(max(col))
for i in e:
	print(col[i])


from collections import deque, defaultdict
N = int(input())
d = defaultdict(list)
m = dict()
ls = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
	ls.append((a, b))
K = 0
for i in range(N):
	d[i + 1].sort()
	K = max(K, len(d[i + 1]))
print(K)
q = deque([])
q.append((1, 0))
visited = [0 for i in range(N + 1)]
visited[1] = 1
while q:
	(l, r) = q.popleft()
	flag = 0
	cur = 1
	for (i, x) in enumerate(d[l], start=1):
		if visited[x] == 1:
			continue
		if flag == 0:
			if cur == r:
				q.append((x, cur + 1))
				m[l, x] = cur + 1
				m[x, l] = cur + 1
				cur += 2
				visited[x] = 1
				flag = 1
				continue
			m[l, x] = cur
			m[x, l] = cur
			q.append((x, cur))
			cur += 1
			visited[x] = 1
		else:
			q.append((x, cur))
			m[l, x] = cur
			m[x, l] = cur
			cur += 1
			visited[x] = 1
for i in range(N - 1):
	(a, b) = ls[i]
	print(m[a, b])


n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append((b - 1, i))
vc = [0] * n
ec = [-1] * (n - 1)
for (p, ci) in enumerate(g):
	color = 1
	for (c, i) in ci:
		if vc[p] == color:
			color += 1
		vc[c] = color
		ec[i] = color
		color += 1
print(max(ec))
for i in range(n - 1):
	print(ec[i])


import sys
sys.setrecursionlimit(10 ** 8)

def dfs(v, c):
	now = 1
	for (u, i) in edge[v]:
		if color[i] == 0:
			if now == c:
				now += 1
			color[i] = now
			dfs(u, now)
			now += 1
	return 0
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append([b - 1, i])
	edge[b - 1].append([a - 1, i])
color = [0] * (N - 1)
dfs(0, 1 << 30)
print(max(color))
print(*color, sep='\n')


import sys
from collections import deque
n = int(input())
G = [[] for _ in range(n + 1)]
G_order = []
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	G[a].append(b)
	G_order.append(b)
que = deque([0])
colors = [0] * n
while que:
	prt = que.popleft()
	color = 0
	for cld in G[prt]:
		color += 1
		if color == colors[prt]:
			color += 1
		colors[cld] = color
		que.append(cld)
print(max(colors))
for i in G_order:
	print(colors[i])


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])
(dy8, dx8) = ([0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def sum_of_arithmetic_progression(s, d, n):
	return n * (2 * s + (n - 1) * d) // 2

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	g = gcd(a, b)
	return a / g * b

def dfs(u, p, c, color, tree):
	color[u, p] = c
	color[p, u] = c
	now = 0
	for v in tree[u]:
		if v == p:
			continue
		if now == c:
			now += 1
		dfs(v, u, now, color, tree)
		now += 1

def solve():
	N = int(input())
	tree = [[] for _ in range(N)]
	edges = []
	for _ in range(N - 1):
		(A, B) = list(map(int, input().split()))
		A -= 1
		B -= 1
		tree[A].append(B)
		tree[B].append(A)
		edges.append((A, B))
	color = dict()
	dfs(0, -1, -1, color, tree)
	print(max(color.values()) + 1)
	for e in edges:
		print(color[e] + 1)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


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, i))
node_color = [0] * n
branch_color = [0] * (n - 1)
for (start_node, goal) in enumerate(g):
	color = 1
	for (goal_node, i) in goal:
		if node_color[start_node] == color:
			color += 1
		node_color[goal_node] = color
		branch_color[i] = color
		color += 1
print(max(branch_color))
for i in branch_color:
	print(i)


import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
es = [[] for i in range(N)]
for (i, (a, b)) in enumerate(AB):
	(a, b) = (a - 1, b - 1)
	es[a].append((b, i))
	es[b].append((a, i))
ans = [0] * (N - 1)
g = [0] * N

def dfs(v, h=-1):
	res = 1
	for (i, j) in es[v]:
		if g[i]:
			continue
		g[v] = 1
		if h == res:
			res += 1
		ans[j] = res
		dfs(i, res)
		res += 1
dfs(0)
print(max(ans))
for i in ans:
	print(i)


N = int(input())
graph = [[] for _ in range(N + 1)]
AB = []
for _ in range(N - 1):
	(a, b) = list(map(int, input().split()))
	graph[a].append(b)
	graph[b].append(a)
	AB.append((a, b))
root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)
color = [-1] * (N + 1)
K = -1
for x in order:
	ng = color[x]
	c = 1
	for y in graph[x]:
		if y == parent[x]:
			continue
		if c == ng:
			c += 1
		K = max(c, K)
		color[y] = c
		c += 1
ans = []
for (a, b) in AB:
	if parent[a] == b:
		ans.append(color[a])
	else:
		ans.append(color[b])
print(K)
for i in ans:
	print(i)


from collections import deque, defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	data[a].append(b)
	data[b].append(a)
	sides.append((a, b))
I = defaultdict(lambda : 0)
cs = [0] * n
used = [0] * n
q = deque([0])
used[0] = 1
k = 0
while q:
	u = q.popleft()
	if k < len(data[u]):
		k = len(data[u])
	cur = 1
	for v in data[u]:
		if used[v]:
			continue
		if cur == cs[u]:
			cur += 1
		cs[v] = cur
		I[u, v] = cur
		I[v, u] = cur
		cur += 1
		used[v] = 1
		q.append(v)
print(k)
for (i, j) in sides:
	print(I[i, j])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	links[a].append((b, i))

def dfs(a, color):
	c = 1
	for (b, i) in links[a]:
		if c == color:
			c += 1
		colors[i] = c
		dfs(b, c)
		c += 1
dfs(0, 0)
print(max(colors))
for color in colors:
	print(color)


N = int(input())
inp = []
for k in range(N - 1):
	(a, b) = list(map(int, input().split()))
	if a > b:
		(a, b) = (b - 1, a - 1)
	else:
		(a, b) = (a - 1, b - 1)
	inp.append((a, b, k))
inp.sort(key=lambda x: x[0])
mark = [[] for _ in range(N)]

def binary_search(list, item):
	low = 0
	high = len(list) - 1
	while low <= high:
		mid = (low + high) // 2
		guess = list[mid]
		if guess == item:
			return True
		if guess > item:
			high = mid - 1
		else:
			low = mid + 1
	return False
from bisect import insort
ans = [0 for _ in range(N - 1)]
now = 0
cnt = 0
for item in inp:
	cnt += 1
	if now < item[0]:
		now = item[0]
		cnt = 1
	while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
		cnt += 1
	insort(mark[item[1]], cnt)
	ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N - 1):
	print(ans[k])


import sys
from collections import deque
inputs = sys.stdin.readlines()
n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
to_edges = [e[1] for e in edges]
tree = [[] for _ in range(n + 1)]
for (x, y) in edges:
	tree[x].append(y)
queue = deque([1])
colors = [0] * (n + 1)
while queue:
	x = queue.popleft()
	c = 0
	for y in tree[x]:
		c += 1 + (c + 1 == colors[x])
		colors[y] = c
		queue.append(y)
print(max(colors))
for e in to_edges:
	print(colors[e])


N = int(input())
ans = [-1] * (N - 1)
rootLine = [0] * N
numLine = [0] * N
l = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	l.append([a, b, i])
l.sort()
for (a, b, i) in l:
	numLine[a] += 1
	if numLine[a] == rootLine[a]:
		numLine[a] += 1
	ans[i] = numLine[a]
	rootLine[b] = numLine[a]
print(max(ans))
for i in ans:
	print(i)


import queue
n = int(input())
cf = [0] * n
cg = [0] * (n - 1)
ce = [[] for _ in range(n)]
e = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	e[a - 1] += [b - 1]
	e[b - 1] += [a - 1]
	ce[a - 1] += [i]
	ce[b - 1] += [i]
k = len(max(e, key=len))
q = queue.Queue()
q.put(0)
while not q.empty():
	now = q.get()
	cf[now] = 1
	c = 0
	for i in ce[now]:
		if cg[i]:
			c = cg[i]
	j = 1
	for i in ce[now]:
		if j == c:
			j += 1
		if cg[i]:
			continue
		cg[i] = j
		j += 1
	for i in e[now]:
		if cf[i]:
			continue
		q.put(i)
print(k)
for i in cg:
	print(i)


import sys
sys.setrecursionlimit(10 ** 8)

def dfs(x, c=-1, p=-1):
	k = 1
	for (y, ei) in G[x]:
		if y == p:
			continue
		if k == c:
			k += 1
		ans[ei] = k
		k += 1
		dfs(y, ans[ei], x)
n = int(input())
G = [[] for _ in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append((b, i))
	G[b].append((a, i))
dfs(0)
mx = 0
for g in G:
	mx = max(mx, len(g))
print(mx)
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
Edges = []
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
	Edges.append((a - 1, b - 1))
Col = 0
for n in range(N):
	Col = max(Col, len(graph[n]))
Color = dict()
checked = [-1] * N
q = [0]
checked[0] = Col + 1
while q:
	qq = []
	for p in q:
		c = checked[p]
		t = 0
		for np in graph[p]:
			if checked[np] == -1:
				if t == c:
					t += 1
				checked[np] = t
				Color[p, np] = t
				Color[np, p] = t
				t += 1
				qq.append(np)
	q = qq
print(Col)
for (a, b) in Edges:
	print(Color[a, b] + 1)


from collections import deque
n = int(input())
r = [[] for _ in range(n)]
kumi = []
for _ in range(n - 1):
	s = list(map(int, input().split()))
	kumi.append(str(s[0] - 1) + '+' + str(s[1] - 1))
	r[s[0] - 1].append(s[1] - 1)
	r[s[1] - 1].append(s[0] - 1)
ans = 0
for i in range(n):
	ans = max(len(r[i]), ans)
print(ans)
ans_iro = [[] for _ in range(n)]
iro = [-1 for _ in range(n)]
iro[0] = 1
ch = 1
d = []
di = {}
for i in r[0]:
	iro[i] = ch
	di[str(min(0, i)) + '+' + str(max(0, i))] = ch
	ch += 1
	d.append(i)
d = deque(d)
while d:
	v = d.popleft()
	ch = 1
	for i in r[v]:
		if iro[i] == -1:
			if ch == iro[v]:
				ch += 1
				iro[i] = ch
				di[str(min(v, i)) + '+' + str(max(v, i))] = ch
				ch += 1
			else:
				iro[i] = ch
				di[str(min(v, i)) + '+' + str(max(v, i))] = ch
				ch += 1
			d.append(i)
for g in kumi:
	print(di[g])


N = int(input())
ans = [0] * (N - 1)
to = [[] for i in range(N - 1)]
used = [0] * N
for i in range(N - 1):
	(a, b) = map(int, input().split())
	to[a - 1].append([b - 1, i])
for i in range(N - 1):
	unable = used[i]
	c = 1
	for (j, id) in to[i]:
		if c == unable:
			c += 1
		ans[id] = c
		used[j] = c
		c += 1
print(max(used))
for i in range(N - 1):
	print(ans[i])


N = int(input())
edges = [[] for _ in range(N)]
for i in range(N - 1):
	(fr, to) = map(lambda a: int(a) - 1, input().split())
	edges[fr].append((i, to))
	edges[to].append((i, fr))
ans = [-1] * (N - 1)
A = [set() for _ in range(N)]
st = [0]
while st:
	now = st.pop()
	s = 1
	for (i, to) in edges[now]:
		if ans[i] != -1:
			continue
		while s in A[now]:
			s += 1
		ans[i] = s
		A[to].add(s)
		A[now].add(s)
		st.append(to)
print(max(ans))
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
n = int(input())
ans = [0] * (n - 1)
edges = [[] for _ in range(n)]
used = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append([b - 1, i])
for node in range(n):
	unable = used[node]
	color = 1
	for (to, id) in edges[node]:
		if color == unable:
			color += 1
		ans[id] = color
		used[to] = color
		color += 1
print(max(used))
for color in ans:
	print(color)


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, i])
	g[b - 1].append([a - 1, i])
from collections import deque
d = deque([(0, -1)])
ans = [0 for i in range(n - 1)]
while d:
	(a, noc) = d.popleft()
	c = 1 if noc != 1 else 2
	for (b, i) in g[a]:
		if ans[i] == 0:
			ans[i] = c
			d.append((b, c))
		else:
			continue
		c += 1 if c + 1 != noc else 2
print(max(ans))
for i in range(n - 1):
	print(ans[i])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
es = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	es[a - 1].append((b - 1, i))
ans = [0] * (n - 1)

def coloring(vi, prev_color):
	color = 1
	for (to, i) in es[vi]:
		if color == prev_color:
			color += 1
		ans[i] = color
		coloring(to, color)
		color += 1
coloring(0, 0)
print(max(ans))
print(*ans, sep='\n')


from collections import deque
n = int(input())
tree = [[] for _ in range(n + 1)]
for i in range(1, n):
	(a, b) = map(int, input().split())
	tree[a].append([b, i])
	tree[b].append([a, i])
queue = deque([[1, 0]])
ans = [0] * (n + 1)
ans[1] = 1
visited = [0] * (n + 1)
while queue:
	(v, c) = queue.popleft()
	color = 1
	for (nv, i) in tree[v]:
		if c == color:
			color += 1
		if visited[i] == 1:
			continue
		visited[i] = 1
		queue.append([nv, color])
		ans[i] = color
		color += 1
print(max(ans))
for i in range(1, n):
	print(ans[i])


from collections import deque

def solve(N, ABs):
	tree_top = [[] for _ in range(N + 1)]
	for i in range(N - 1):
		tree_top[ABs[i][0]].append(i)
		tree_top[ABs[i][1]].append(i)
	max_color = 0
	for tt in tree_top:
		max_color = max(max_color, len(tt))
	ans = [0 for _ in range(N - 1)]
	for tt in tree_top:
		colored = []
		for i in tt:
			if ans[i] != 0:
				colored.append(ans[i])
		colored.sort()
		now_color = 1
		colored_point = 0
		for i in tt:
			if ans[i] != 0:
				continue
			if colored_point < len(colored) and now_color == colored[colored_point]:
				now_color += 1
				colored_point += 1
			ans[i] = now_color
			now_color += 1
	print(max_color)
	for a in ans:
		print(a)

def __starting_point():
	N = int(input())
	ABs = [[int(i) for i in input().split()] for _ in range(N - 1)]
	solve(N, ABs)
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
M = [set() for _ in range(N)]
A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	A[a - 1].append((b - 1, i))
	A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
	cnt = 1
	for a in A[x]:
		if a[0] == pre:
			continue
		if cnt == p:
			cnt += 1
		ans[a[1]] = cnt
		cnt += 1
		dfs(a[0], ans[a[1]], x)
dfs(0, -1, -1)
print(max(ans))
for a in ans:
	print(a)


import sys

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

def ii():
	return int(input())

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

def li():
	return list(mi())
from collections import deque

def main():
	n = ii()
	edge = [[] for _ in range(n)]
	ans = [0] * (n - 1)
	for i in range(n - 1):
		(u, v) = mi()
		u -= 1
		v -= 1
		edge[u].append((v, i))
		edge[v].append((u, i))
	k = 0
	q = deque([0])
	visited = [False] * n
	visited[0] = True
	c = [0] * n
	while q:
		v = q.popleft()
		cur = 1
		k = max(k, len(edge[v]))
		for (nv, idx) in edge[v]:
			if visited[nv]:
				continue
			if cur == c[v]:
				cur += 1
			visited[nv] = True
			c[nv] = cur
			ans[idx] = cur
			cur += 1
			q.append(nv)
	print(k)
	print(*ans, sep='\n')

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(500000)
n = int(input())
lis = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	lis[a].append((b, i))
	lis[b].append((a, i))
k = max((len(li) for li in lis))
print(k)
ans = [-1] * (n - 1)

def dfs(v=1, p=0, p_col=-1):
	col = 1
	for (u, idx) in lis[v]:
		if u != p:
			if col == p_col:
				col += 1
			ans[idx] = col
			dfs(u, v, col)
			col += 1
dfs()
print('\n'.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append((b - 1, i))
	edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)

def dfs(node, pc):
	color = 1
	for (to, idx) in edge[node]:
		if ec[idx] == 0:
			if color == pc:
				color += 1
			ec[idx] = color
			dfs(to, color)
			color += 1
dfs(0, -1)
print(max(ec))
for c in ec:
	print(c)


n = int(input())
paths = [[] for i in range(n)]
colors = [0] * (n - 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	paths[a - 1].append(i)
	paths[b - 1].append(i)
m = 0
for i in range(n):
	m = max(m, len(paths[i]))
print(m)
for i in range(n):
	(cand1, cand2) = (set(), [])
	for j in paths[i]:
		if colors[j] != 0:
			cand1.add(colors[j])
		else:
			cand2.append(j)
	now = 1
	for j in cand2:
		while now in cand1:
			now += 1
		colors[j] = now
		now += 1
for i in range(n - 1):
	print(colors[i])


N = int(input())
tree = {}
ans = [0 for _ in range(N - 1)]
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	tree.setdefault(a, []).append(i)
	tree.setdefault(b, []).append(i)
for (k, v) in tree.items():
	a = set(range(1, len(v) + 1))
	b = set([ans[i] for i in v])
	if 0 in b:
		b.remove(0)
	a = list(a - b)
	c = 0
	for i in v:
		if ans[i] == 0:
			ans[i] = a[c]
			c += 1
print(max(ans))
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())

def dfs(u, par):
	col = 1
	for v in graph[u]:
		if col == par:
			col += 1
		color_dic[u, v] = col
		dfs(v, col)
		col += 1
elist = []
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	elist.append((a, b))
color_dic = {}
dfs(1, -1)
K = len(set(color_dic.values()))
print(K)
for e in elist:
	print(color_dic[e])


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)
for i in range(1, N):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	numOfEdges[a] += 1
	numOfEdges[b] += 1
	edges[a, b] = 0
	graph[a].append(b)
	graph[b].append(a)

def dfs(prev, now, col):
	if visited[now]:
		return
	visited[now] = 1
	i = 1
	for adj in graph[now]:
		if adj == prev:
			continue
		if now < adj:
			edges[now, adj] = col + i
		else:
			edges[adj, now] = col + i
		dfs(now, adj, col + i)
		i += 1
dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)
for (k, i) in list(edges.items()):
	e = i % maxColor
	if e:
		print(e)
	else:
		print(maxColor)


import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
G = [list() for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append([b, i])
	G[b].append([a, i])

def dfs(v, c=-1, p=-1):
	k = 1
	for i in range(len(G[v])):
		u = G[v][i][0]
		ei = G[v][i][1]
		if u == p:
			continue
		if k == c:
			k += 1
		ans[ei] = k
		k += 1
		dfs(u, ans[ei], v)
dfs(0)
k = max(map(len, G))
print(k)
for i in range(N - 1):
	print(ans[i])


N = int(input())
AB = [list(map(int, input().split())) for i in range(N - 1)]
l = [[] for i in range(N)]
e = [0] * (N - 1)
for (i, (a, b)) in enumerate(AB):
	l[a - 1].append((b - 1, i))
	l[b - 1].append((a - 1, i))
from collections import deque
q = deque([(AB[0][0] - 1, 1), (AB[0][1] - 1, 1)])
e[0] = 1
M = 1
while q:
	(vp, c) = q.popleft()
	x = 1
	for (vn, en) in l[vp]:
		if e[en] == 0:
			if x == c:
				x = c + 1
			q.append((vn, x))
			e[en] = x
			M = max(M, x)
			x += 1
print(M)
print(*e, sep='\n')


from collections import deque
N = int(input())
E = []
G = {i: set() for i in range(1, N + 1)}
c = [-1 for i in range(N - 1)]
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	E.append({a, b})
	G[a].add(i)
	G[b].add(i)
Q = deque([0])
c[0] = 1
while Q:
	i = Q.popleft()
	(a, b) = E[i]
	n = len(G[a])
	color = 0
	count = 0
	for ni in G[a]:
		if c[ni] == -1:
			c[ni] = color + 1
			if c[ni] >= c[i]:
				c[ni] += 1
			color += 1
			Q.append(ni)
		else:
			count += 1
			if count > 1:
				break
	n = len(G[b])
	color = 0
	count = 0
	for ni in G[b]:
		if c[ni] == -1:
			c[ni] = color + 1
			if c[ni] >= c[i]:
				c[ni] += 1
			color += 1
			Q.append(ni)
		else:
			count += 1
			if count > 1:
				break
print(max(c))
for i in c:
	print(i)


import sys
read = sys.stdin.read
(n, *ab) = map(int, read().split())
ans = [0] * (n - 1)
edges = [[] for _ in range(n)]
used = [0] * n
for (i, a, b) in zip(range(n - 1), *[iter(ab)] * 2):
	edges[a - 1].append([b - 1, i])
for node in range(n):
	unable = used[node]
	color = 1
	for (to, id) in edges[node]:
		if color == unable:
			color += 1
		ans[id] = str(color)
		used[to] = color
		color += 1
print(max(used))
print('\n'.join(ans))


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
t = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	t[a].append((b, i))
	t[b].append((a, i))
num = max([len(tmp) for tmp in t])
print(num)
ans = [-1] * (n - 1)

def dfs(n, before, bcol):
	col = 1
	for (i, j) in t[n]:
		if i == before:
			continue
		if col == bcol:
			col += 1
		ans[j] = col
		dfs(i, n, col)
		col += 1
dfs(1, 0, -1)
for i in range(n - 1):
	print(ans[i])


N = int(input())
from collections import defaultdict
from collections import deque
g = defaultdict(list)
idx = defaultdict(int)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	idx[a, b] = i
q = deque()
q.append((1, 0))
res = [0] * (N - 1)
n = 0
while q:
	(node, color) = q.popleft()
	n = max(n, color)
	i = 1
	for nei in g[node]:
		if i == color:
			i += 1
		q.append((nei, i))
		res[idx[node, nei]] = i
		i += 1
print(n)
for c in res:
	print(c)


from collections import defaultdict as dd, Counter
N = int(input())
edges = [None] * (N - 1)
es = dd(dict)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	es[a][b] = es[b][a] = i
q = []
q.append((1, -1))
while q:
	(i, used) = q.pop()
	color = 0
	for (to, eid) in es[i].items():
		if edges[eid] is not None:
			continue
		color += 1
		if color == used:
			color += 1
		edges[eid] = color
		q.append((to, color))
ct = Counter(edges)
print(len(ct))
for e in edges:
	print(e)


import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split(' '))
	E[a].append((b, i))
	E[b].append((a, i))
K = max((len(e) for e in E))
print(K)
ans = [-1] * (N - 1)

def dfs(v=1, p=0, p_col=-1):
	col = 1
	for (u, idx) in E[v]:
		if u != p:
			if col == p_col:
				col += 1
			ans[idx] = col
			dfs(u, v, col)
			col += 1
dfs()
for i in ans:
	print(i)


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

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

def MAP1():
	return map(lambda x: int(x) - 1, input().split())

def LIST():
	return list(MAP())

def solve():
	n = INT()
	Q = [tuple(MAP1()) for _ in range(n - 1)]
	deg = [0] * n
	adj = [[] for _ in range(n)]
	color = dict()
	for (a, b) in Q:
		deg[a] += 1
		deg[b] += 1
		adj[a].append(b)
		adj[b].append(a)

	def dfs(s, p):
		nouse = -1
		if p > -1:
			nouse = color[min(s, p), max(s, p)]
		c = 1
		for t in adj[s]:
			if t == p:
				continue
			if c == nouse:
				c += 1
			color[min(s, t), max(s, t)] = c
			dfs(t, s)
			c += 1
	dfs(1, -1)
	print(max(deg))
	for (a, b) in Q:
		print(color[a, b])

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append((b, i))
	g[b].append((a, i))
ans = [0] * (n - 1)

def dfs(u, c=-1, p=-1):
	k = 1
	for (v, i) in g[u]:
		if v == p:
			continue
		if k == c:
			k += 1
		ans[i] = k
		k += 1
		dfs(v, ans[i], u)
dfs(0)
print(max(ans))
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(9 ** 9)
n = int(input())
T = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	T[a - 1].append([b - 1, i])
C = [0] * (n - 1)

def f(i, r):
	c = 1
	for (x, y) in T[i]:
		c += c == r
		C[y] = c
		f(x, c)
		c += 1
f(0, 0)
print(max(C))
for c in C:
	print(c)


import sys
sys.setrecursionlimit(10 ** 7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor

def cmb(n, r, mod):
	bunshi = 1
	bunbo = 1
	for i in range(r):
		bunbo = bunbo * (i + 1) % mod
		bunshi = bunshi * (n - i) % mod
	return bunshi * pow(bunbo, mod - 2, mod) % mod
mod = 10 ** 9 + 7

def I():
	return int(input())

def LI():
	return list(map(int, input().split()))

def MI():
	return list(map(int, input().split()))

def LLI(n):
	return [list(map(int, input().split())) for _ in range(n)]
n = I()
graph = [[] for _ in range(n + 1)]
prev_col = [0] * (n + 1)
a_b = []
k = 0
for i in range(n - 1):
	(a, b) = MI()
	a_b.append(str(a) + ' ' + str(b))
	graph[a].append(b)
	graph[b].append(a)
check = [-1] * (n + 1)
check[0] = 0
check[1] = 0
for i in range(n + 1):
	k = max(len(graph[i]), k)
d = deque()
d.append(1)
ans = dict()
while d:
	v = d.popleft()
	check[v] = 1
	cnt = 0
	for i in graph[v]:
		if check[i] != -1:
			continue
		cnt = cnt + 1
		if prev_col[v] == cnt:
			cnt = cnt + 1
		prev_col[i] = cnt
		ans[str(min(i, v)) + ' ' + str(max(i, v))] = cnt
		d.append(i)
print(k)
for key in a_b:
	print(ans[key])


import sys
input = sys.stdin.readline
n = int(input())
edge = {}
tree = [[] for i in range(n)]
color = [0] * (n - 1)
color_par = [-1] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append(b)
	edge[a, b] = i
for i in range(n):
	c = 1
	for v_child in tree[i]:
		if c == color_par[i]:
			c += 1
		color[edge[i, v_child]] = c
		color_par[v_child] = c
		c += 1
print(max(color))
print(*color, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	v[a].append([b, i])
ans = [None] * (N - 1)

def decide_colord(cur, color):
	cnt = 1
	for (to, j) in v[cur]:
		if cnt == color:
			cnt += 1
		ans[j] = cnt
		decide_colord(to, cnt)
		cnt += 1
decide_colord(0, 0)
print(max(ans))
[print(a) for a in ans]


import sys
from collections import deque
inputs = sys.stdin.readlines()
n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
B = [e[1] for e in edges]
E = [[] for _ in range(n + 1)]
for (a, b) in edges:
	E[a].append(b)
Q = deque([1])
C = [0] * (n + 1)
while Q:
	v = Q.popleft()
	c = 0
	for u in E[v]:
		c += 1 + (c + 1 == C[v])
		C[u] = c
		Q.append(u)
print(max(C))
for b in B:
	print(C[b])


n = int(input())
G = [[] for i in range(n + 1)]
G_order = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G_order.append(b)
from collections import deque
q = deque([1])
color = [0] * (n + 1)
while q:
	cur = q.popleft()
	c = 1
	for nx in G[cur]:
		if c == color[cur]:
			c += 1
		color[nx] = c
		c += 1
		q.append(nx)
print(max(color))
for i in G_order:
	print(color[i])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n = int(input())
E = [[] for _ in range(n)]
C = [0 for i in range(n - 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append([b - 1, i])
	E[b - 1].append([a - 1, i])
c = 1

def dfs(cur, pre, pre_c):
	c = 1
	for (e, i) in E[cur]:
		if e != pre:
			if c == pre_c:
				c += 1
			C[i] = c
			dfs(e, cur, c)
			c += 1
dfs(0, -1, 0)
print(max(C))
for item in C:
	print(item)


import sys
import math
from collections import deque
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def make_grid(h, w, num):
	return [[int(num)] * w for _ in range(h)]

def make_adjlist_nond(n, edges):
	res = [[] for _ in range(n + 1)]
	for edge in edges:
		res[edge[0]].append(edge[1])
		res[edge[1]].append(edge[0])
	return res

def main():
	N = NI()
	edges = [NLI() for _ in range(N - 1)]
	graph = [[] for _ in range(N + 1)]
	edge_dict = {}
	for (i, edge) in enumerate(edges):
		graph[edge[0]].append(edge[1])
		graph[edge[1]].append(edge[0])
		edge_dict[edge[0], edge[1]] = i + 1
	queue = deque()
	queue.append(1)
	seen = [0] * (N + 1)
	colors = [-1] * N
	colors[1] = 1
	now_colors = deque()
	now_colors.append(-1)
	while queue:
		now = queue.popleft()
		now_color = now_colors.popleft()
		seen[now] = 1
		nexts = graph[now]
		color = 1
		for goto in nexts:
			if seen[goto] == 0:
				(a, b) = (min(now, goto), max(now, goto))
				if color == now_color:
					color += 1
				colors[edge_dict[a, b]] = color
				queue.append(goto)
				now_colors.append(color)
				color += 1
	print(max(colors))
	for i in range(1, N):
		print(colors[i])

def __starting_point():
	main()
__starting_point()


(n, *L) = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for (a, b) in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
k = max(map(len, con))
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	(cur, ex) = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex == 0 or ex == k)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i == ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
print(k)
for (a, b) in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k if t > k else t)


from collections import deque
n = int(input())
edges_ls = [[0, 0] for _ in range(n - 1)]
edges_d = {}
ver_ls = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edges_d[a, b] = i
	edges_d[b, a] = i
	edges_ls[i] = [a, b]
	ver_ls[a].append(b)
	ver_ls[b].append(a)
n_color = 0
for ver in ver_ls:
	n_color = max(n_color, len(ver))

def next_color(color):
	return (color + 1) % n_color
edge_color = [0] * (n - 1)
q = deque()
color_now = 0
for ver in ver_ls[0]:
	q.append([0, ver, color_now])
	edge_color[edges_d[0, ver]] = color_now
	color_now = next_color(color_now)
done_ls = [0] * n
done_ls[0] = 1
while q:
	(From, to, color_now) = q.popleft()
	for ver in ver_ls[to]:
		if not done_ls[ver]:
			q.append([to, ver, next_color(color_now)])
			edge_color[edges_d[to, ver]] = next_color(color_now)
			color_now = next_color(color_now)
	done_ls[to] = 1
print(n_color)
for color in edge_color:
	print(color + 1)


from collections import deque
(N, *AB) = map(int, open(0).read().split())
E = [set() for _ in range(N + 1)]
memo = {}
for (i, (a, b)) in enumerate(zip(*[iter(AB)] * 2)):
	E[a].add(b)
	E[b].add(a)
	memo[a, b] = i
	memo[b, a] = i
K = max((len(e) for e in E))
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
	(p, v) = Q.popleft()
	C = (c for c in range(1, K + 1) if c != p)
	for u in E[v]:
		E[u].remove(v)
		c = next(C)
		Q.append((c, u))
		A[memo[v, u]] = c
print(K)
for a in A:
	print(a)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
N = int(input())
adj = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append((b, i))
res = [None] * (N - 1)

def dfs(n, c=-1, p=-1):
	if c == -1 or c > 1:
		nc = 1
	else:
		nc = c + 1
	for (nei, i) in adj[n]:
		if nei == p:
			continue
		res[i] = nc
		dfs(nei, nc, n)
		nc += 1
		if nc == c:
			nc += 1
dfs(0)
print(max(res))
for r in res:
	print(r)


import sys
sys.setrecursionlimit(10000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
hen = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = AB[i]
	hen[a - 1].append(b)
ans = {}

def dfs(l, p):
	col = 0
	for i in hen[p - 1]:
		col += 1
		if col == l:
			col += 1
		ans[str(p) + ',' + str(i)] = col
		dfs(col, i)
dfs(-1, 1)
print(max(ans.values()))
for (a, b) in AB:
	print(ans[str(a) + ',' + str(b)])


from collections import deque, defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	edges[a - 1].append([b - 1, i])
	edges[b - 1].append([a - 1, i])
c = 1
col = [0] * (n - 1)
visited = [0] * (n - 1)
que = deque()
for v in edges[0]:
	que.append(v)
	col[v[1]] = c
	visited[v[1]] = 1
	c += 1
while que:
	v = que.popleft()
	c = 1
	used = set()
	for i in edges[v[0]]:
		if visited[i[1]]:
			used.add(col[i[1]])
	for next_v in edges[v[0]]:
		if not visited[next_v[1]]:
			if c in used:
				c += 1
			col[next_v[1]] = c
			used.add(c)
			c += 1
			visited[next_v[1]] = 1
			que.append(next_v)
print(max(col))
for i in col:
	print(i)


N = int(input())
ABs = []
E = [set() for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	ABs.append((a, b))
	E[a].add(b)
	E[b].add(a)
K = max([len(s) for s in E])
print(K)
Is = sorted(range(N - 1), key=lambda i: ABs[i])
cs = [-1] * (N - 1)
V = [-1] * N
for i in range(N - 1):
	j = Is[i]
	(a, b) = ABs[j]
	c = V[a]
	c = (c + 1) % K
	V[a] = c
	V[b] = c
	cs[j] = c
for c in cs:
	print(c + 1)


from collections import deque
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n - 1)]
tree = [[] for _ in range(n)]
for (a, b) in graph:
	tree[a - 1].append(b - 1)
color = [0] * n
q = deque([0])
while q:
	c = 1
	x = q.popleft()
	for i in tree[x]:
		if c == color[x]:
			c += 1
		color[i] = c
		c += 1
		q.append(i)
print(max(color))
for j in range(n - 1):
	print(color[graph[j][1] - 1])


from collections import deque
n = int(input())
tree = [[] for i in range(n + 1)]
edge = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
	edge.append((a, b))
m = len(max(tree, key=len))
col = [0] * (n + 1)
col[1] = 'a'
Q = deque([1])
ans = {}
while Q:
	temp = Q.popleft()
	now = 1
	for n in tree[temp]:
		if col[n]:
			continue
		if now == col[temp]:
			now += 1
		col[n] = now
		ans[min(temp, n), max(temp, n)] = now
		now += 1
		Q.append(n)
print(m)
for (a, b) in edge:
	print(ans[a, b])


from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	E[a].append([i, b])
	E[b].append([i, a])
k = 0
for e in E:
	k = max(k, len(e))
print(k)

def bfs():
	colors = [-1 for _ in range(N - 1)]
	visited = [False for _ in range(N)]
	d = deque()
	d.append([0, -1])
	while d:
		(now, edge_color) = d.pop()
		visited[now] = True
		cand_color = 1
		for (i, nxt) in E[now]:
			if visited[nxt]:
				continue
			if colors[i] > -1:
				assert '１エッジに２色塗ろうとする・・・？'
				continue
			if cand_color == edge_color:
				cand_color += 1
			colors[i] = cand_color
			d.append([nxt, colors[i]])
			cand_color += 1
	return colors
colors = bfs()
for i in range(len(colors)):
	print(colors[i])


N = int(input())
AB = [list(map(int, input().split())) for _ in [0] * (N - 1)]
E = [[] for _ in [0] * N]
for (i, ab) in enumerate(AB):
	(a, b) = ab
	a -= 1
	b -= 1
	E[a].append((b, i))
	E[b].append((a, i))
done = [False] * N
done[0] = True
ans = [0] * (N - 1)
q = [(0, 0)]
while q:
	(i, c0) = q.pop()
	c = 1
	for (j, ei) in E[i]:
		if done[j]:
			continue
		done[j] = True
		if c == c0:
			c += 1
		q.append((j, c))
		ans[ei] = c
		c += 1
print(max(ans))
for out in ans:
	print(out)


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, list(input().split()))
	edges[a - 1].append((b - 1, i))
ans = [0] * (n - 1)

def f(a, c):
	color = 1
	for (b, i) in edges[a]:
		if color == c:
			color += 1
		ans[i] = color
		f(b, color)
		color += 1
f(0, 0)
print(max(ans))
for i in ans:
	print(i)


import sys
sys.setrecursionlimit(1000000)
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append([b, i])
ans = [None] * (N - 1)

def rec(cur, color):
	cnt = 1
	for (to, j) in G[cur]:
		if cnt == color:
			cnt += 1
		ans[j] = cnt
		rec(to, cnt)
		cnt += 1
rec(0, 0)
print(max(ans))
[print(a) for a in ans]


import sys
sys.setrecursionlimit(500000)
n = int(input())
E = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	E[a].append([b, i])
	E[b].append([a, i])
k = 0
for e in E:
	k = max(k, len(e))
ans = [0] * (n - 1)

def dsf(v, p, vp_c):
	c = 1
	for (u, i) in E[v]:
		if u != p:
			if c == vp_c:
				c += 1
			ans[i] = c
			dsf(u, v, c)
			c += 1
dsf(1, 0, 0)
print(k)
for i in range(n - 1):
	print(ans[i])


from collections import deque
n = int(input())
k = 0
data = [[] for _ in range(n)]
ans_index = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	data[a].append(b)
	ans_index.append(b)
q = deque([0])
color = [0] * n
while q:
	cur = q.popleft()
	c = 1
	for x in data[cur]:
		if c == color[cur]:
			c += 1
		color[x] = c
		c += 1
		q.append(x)
print(max(color))
for i in ans_index:
	print(color[i])


import os
import sys
from collections import deque

class BFS:

	def __init__(self, path, N):
		self.N = N
		self.color_path = [-1] * self.N
		self.path = path
		self.init = 1
		self.Q = deque([[0, self.init]])

	def forward(self):
		while self.Q:
			(prev_path, u) = self.Q.popleft()
			p_cnt = 1
			for (cp, v) in self.path[u]:
				if self.color_path[cp] == -1:
					if prev_path == p_cnt:
						p_cnt += 1
					self.Q.append([p_cnt, v])
					self.color_path[cp] = p_cnt
					p_cnt += 1

	def print_ans(self):
		self.color_path.pop(0)
		print(max(self.color_path))
		for cp in self.color_path:
			print(cp)

def main():
	N = int(input())
	path = [[] for _ in range(N + 1)]
	for i in range(1, N):
		(a, b) = list(map(int, input().split()))
		path[a].append([i, b])
		path[b].append([i, a])
	bfs = BFS(path, N)
	bfs.forward()
	bfs.print_ans()

def __starting_point():
	main()
__starting_point()


import sys
from collections import deque
n = int(sys.stdin.readline())
G = [[] for _ in range(n + 1)]
G_order = []
for i in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, sys.stdin.readline().split())
	G[a].append(b)
	G_order.append(b)
que = deque([0])
C = [0] * (n + 1)
while que:
	nw = que.popleft()
	c = 1
	for nx in G[nw]:
		if c == C[nw]:
			c += 1
		C[nx] = c
		c += 1
		que.append(nx)
print(max(C))
for i in G_order:
	print(C[i])


from collections import defaultdict, deque
(N, *AB) = map(int, open(0).read().split())
g = defaultdict(set)
edges = []
for (a, b) in zip(*[iter(AB)] * 2):
	a -= 1
	b -= 1
	g[a].add(b)
	g[b].add(a)
	edges.append((a, b))
q = deque([0])
visited = [False] * N
visited[0] = True
used = [0] * N
colors_cnt = 1
ans = {}
while q:
	v = q.popleft()
	color = 1
	for nv in g[v]:
		if visited[nv]:
			continue
		if color == used[v]:
			color += 1
		used[nv] = color
		ans[min(v, nv), max(v, nv)] = color
		color += 1
		q.append(nv)
		visited[nv] = True
	colors_cnt = max(colors_cnt, color - 1)
print(colors_cnt)
[print(ans[a, b]) for (a, b) in edges]


from collections import deque
N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]
tree = [[] for _ in range(N)]
for (n, (i, j)) in enumerate(X):
	tree[i - 1].append((n, j - 1))
q = deque()
q.append((0, 0))
ans = [0] * (N - 1)
while len(q) > 0:
	(u, c) = q.popleft()
	cnt = 1
	for (i, (n, v)) in enumerate(tree[u]):
		if cnt == c:
			cnt += 1
		ans[n] = cnt
		q.append((v, cnt))
		cnt += 1
print(max(ans))
print(*ans, sep='\n')


from collections import deque
n = int(input())
K = 0
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].append([b, i])
	g[b].append([a, i])
for i in range(n):
	K = max(len(g[i]), K)
print(K)
ans = [0] * (n - 1)
q = deque([(-1, 1)])
while q:
	(s, p) = q.popleft()
	C = (c for c in range(1, K + 1) if c != s)
	for (i, j) in g[p]:
		g[i].remove([p, j])
		sa = next(C)
		ans[j] = sa
		q.append((sa, i))
for i in ans:
	print(i)


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
N = int(input())
Gb = [[] for _ in range(N)]
Gu = [[] for _ in range(N)]
Es = {}
for n in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	Es[f'{a:06}{b:06}'] = None
	Gb[a].append(b)
	Gb[b].append(a)
	Gu[a].append(b)
colors = list(range(max(map(len, Gb))))

def dfs(base_node, edge_color):
	nonlocal Es
	valid_colors = filter(lambda color: color != edge_color, colors)
	for (child_node, color) in zip(Gu[base_node], valid_colors):
		Es[f'{base_node:06}{child_node:06}'] = color + 1
		dfs(child_node, color)
print(len(colors))
dfs(0, None)
for color in Es.values():
	print(color)


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
graph = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append([b, i])
	graph[b].append([a, i])
ans = [None] * (N - 1)

def dfs(cur, p_color, p=-1):
	color = 1
	for (to, i) in graph[cur]:
		if to == p:
			continue
		if color == p_color:
			color = color + 1
		ans[i] = color
		dfs(to, color, p=cur)
		color = color + 1
dfs(0, -1)
print(max(ans))
[print(a) for a in ans]


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append([b, i])
ans = [None] * (n - 1)

def rec(cur, color):
	count = 1
	for (to, j) in G[cur]:
		if count == color:
			count += 1
		ans[j] = count
		rec(to, count)
		count += 1
rec(0, 0)
print(max(ans))
print(*ans, sep='\n')


N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append((b - 1, i))
	E[b - 1].append((a - 1, i))
C = [0] * (N - 1)
stack = [0]
max_c = 0
while stack:
	n = stack.pop()
	u = set()
	for (to, i) in E[n]:
		if C[i] != 0:
			u.add(C[i])
	c = 1
	for (to, i) in E[n]:
		if C[i] != 0:
			continue
		while c in u:
			c += 1
		C[i] = c
		max_c = max(max_c, c)
		c += 1
		stack.append(to)
print(max_c)
print('\n'.join(map(str, C)))


from sys import setrecursionlimit
setrecursionlimit(100000)
N = int(input())
adj = [list() for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	adj[a].append((b, i))
	adj[b].append((a, i))
res = [None] * (N - 1)
C = max((len(l) for l in adj))

def rec(v, used):
	global res
	c = 0
	for (u, i) in adj[v]:
		if c == used:
			c += 1
		if res[i] is None:
			res[i] = c
			rec(u, c)
			c += 1
rec(0, -1)
print(C)
for c in res:
	print(c + 1)


n = int(input())
l = [[] for _ in range(n)]
li = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	l[a - 1].append(b - 1)
	li.append([a - 1, b - 1])
ans = [-1] * n
for i in range(n):
	x = 0
	for (j, h) in enumerate(l[i]):
		if ans[i] == j:
			x += 1
		ans[h] = j + x
print(max(ans) + 1)
for i in range(n - 1):
	print(ans[li[i][1]] + 1)


import sys
sys.setrecursionlimit(1000000)

def input():
	return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for j in range(n - 1):
	(a, b) = [int(i) - 1 for i in input().split()]
	e[a].append((b, j))
	e[b].append((a, j))
co = [0] * (n - 1)

def dfs(i=0, r=-1, dis=-1):
	global co
	c = 1
	for j in e[i]:
		if j[0] == r:
			continue
		if c == dis:
			c += 1
		co[j[1]] = c
		dfs(j[0], i, c)
		c += 1
dfs()
print(max(co))
for i in co:
	print(i)


(n, *t) = map(int, open(0).read().split())
e = [[] for _ in range(n)]
d = []
for (a, b) in zip(*[iter(t)] * 2):
	e[a - 1] += (b - 1,)
	e[b - 1] += (a - 1,)
	d += ((a - 1, b - 1),)
s = [(0, 0)]
f = [1] + [0] * n
dic = dict()
while s:
	(v, color) = s.pop()
	i = 0
	for w in e[v]:
		if f[w]:
			continue
		f[w] = 1
		i += 1
		if i == color:
			i += 1
		s += ((w, i),)
		dic[v, w] = i
ans = []
for (a, b) in d:
	if (a, b) in dic:
		ans += (dic[a, b],)
	else:
		ans += (dic[b, a],)
print(max(ans))
for t in ans:
	print(t)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
ab = [list(map(int, input().split())) for i in range(N - 1)]
E = [[] for _ in range(N + 1)]
for i in range(N - 1):
	E[ab[i][0]].append(ab[i][1])
color = [0] * (N + 1)
start = 1
q = deque([start])
while q:
	v = q.pop()
	c = 0
	for u in E[v]:
		c += 1 + (c + 1 == color[v])
		color[u] = c
		q.append(u)
print(max(color))
for i in range(N - 1):
	print(color[ab[i][1]])


from collections import deque
N = int(input())
E = [[] for i in range(N + 1)]
edge_order = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a].append(b)
	edge_order.append(b)
queue = deque([1])
color = [0] * (N + 1)
while queue:
	V = queue.popleft()
	c = 1
	for i in E[V]:
		if c == color[V]:
			c += 1
		color[i] = c
		c += 1
		queue.append(i)
print(max(color))
for i in edge_order:
	print(color[i])


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
n = ni()
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = na()
	g[a - 1].append((b - 1, i))
ans = [-1] * (n - 1)
m = [0] * n
for i in range(n):
	k = 1
	for (c, j) in g[i]:
		if m[i] == k:
			k += 1
		m[c] = k
		ans[j] = k
		k += 1
print(max(m))
print('\n'.join([str(u) for u in ans]))


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	N = I()
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = LI_()
		G[a].append((b, i))
		G[b].append((a, i))
	ans = [0] * (N - 1)
	visited = [False] * N

	def dfs(c, color_p):
		visited[c] = True
		color = 0
		for (n, i) in G[c]:
			if not visited[n]:
				if color == color_p:
					color += 1
				ans[i] = color
				dfs(n, color)
				color += 1
	dfs(0, -1)
	print(max(ans) + 1)
	for i in ans:
		print(i + 1)

def __starting_point():
	resolve()
__starting_point()


import sys
stdin = sys.stdin
from collections import deque

def ns():
	return stdin.readline().rstrip()

def ni():
	return int(ns())

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

def main():
	n = ni()
	g = [list() for _ in range(n)]
	to = list()
	for i in range(n - 1):
		(a, b) = na()
		a -= 1
		b -= 1
		g[a].append(b)
		to.append(b)
	l = [-1] * n
	l[0] = 10 ** 10
	q = deque([0])
	while q:
		v = q.popleft()
		vcolor = l[v]
		for (i, w) in enumerate(g[v]):
			q.append(w)
			if i < vcolor:
				l[w] = i
			else:
				l[w] = i + 1
	print(max(l[1:]) + 1)
	for i in to:
		print(l[i] + 1)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
N = int(input())
edge = []
relation = defaultdict(set)
for i in range(N - 1):
	(a, b) = map(lambda x: x - 1, map(int, input().split()))
	edge.append((a, b))
	relation[a].add(b)
	relation[b].add(a)
print(max(map(lambda x: len(relation[x]), relation)))
answer = {}
queue = []
queue.append((0, 0))
already = set()
counter = 0
already.add(0)
while counter < len(queue):
	(node, color) = queue[counter]
	c = 1 if color != 1 else 2
	for n in relation[node]:
		if n not in already:
			queue.append((n, c))
			already.add(n)
			answer[node, n] = c
			c += 1
			if c == color:
				c += 1
	counter += 1
for e in edge:
	print(answer[e])


from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
Q = [{} for _ 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)
	Q[a - 1][b - 1] = i
K = max(list(map(len, G)))
print(K)
ans = [0] * (N - 1)
q = Queue()
q.put(0)
while not q.empty():
	v = q.get()
	c = set()
	for u in G[v]:
		if u < v:
			c.add(ans[Q[u][v]])
	i = 1
	for u in G[v]:
		if u > v:
			while i in c:
				i += 1
			ans[Q[v][u]] = i
			i += 1
			q.put(u)
for a in ans:
	print(a)


f = lambda : map(int, input().split())
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = f()
	g[a - 1] += [(b - 1, i)]
	g[b - 1] += [(a - 1, i)]
l = [0] * (n - 1)
u = [0] * n
q = [(0, 0)]
while q:
	(v, s) = q.pop()
	u[v] = 1
	t = 1
	for (c, i) in g[v]:
		if u[c]:
			continue
		if t == s:
			t += 1
		l[i] = t
		q += [(c, t)]
		t += 1
print(max(l))
for i in l:
	print(i)