CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(eval(input()))
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 0
for i in range(N):
    K = max(K, len(repn[i]))
color_set = set([i for i in range(1, K + 1)])
print(K)

q = [(0, K + 1)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    c_set.discard(color)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.pop()
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))

for pair in edge:
    print((color_dict[pair]))


# Optimized solution
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(eval(input()))
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 1
q = [(0, None)]
while q:
    u, color = q.pop()
    if color == 1:
        c = 2
    else:
        c = 1
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))
            K = max(K, c)
            c += 1
            if c == color:
                c += 1
                

print(K)
for pair in edge:
    print((color_dict[pair]))
# Original solution
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(eval(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()
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                col = 1
                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))))

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(eval(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))))

if __name__ == '__main__':
    main()
# Original solution
N = int(input().strip())

#n_list = [[] for i in range(N)]
d = [0] * N
connect = [[-1 for i in range(N)] for j in range(N)]
for i in range(N-1):
    a, b = list(map(int, input().strip().split()))
    a -= 1
    b -= 1
    connect[a][b] = i
    connect[b][a] = i
    d[a] += 1
    d[b] += 1

max_index = -1
max_degree = -1
for i in range(N):
    if d[i] > max_degree:
        max_degree = d[i]
        max_index = i

colors = [0] * (N-1)

root = max_index

def paint(node, parent_edge_id):
    tmp_color = 1
    for i in range(N):
        edge_id = connect[node][i]
        if edge_id == -1:
            continue
        if edge_id != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge_id] = tmp_color
            paint(i, edge_id)
            tmp_color += 1

    
try:
    paint(root, -1)
except TypeError:
    print((0))
print(max_degree) # color num    a
for i in range(N-1):
    print((colors[i]))

# Optimized solution
import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = list(map(int, input().strip().split()))
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(list(d_dict.items()), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print((tmp[0][1])) # color num 
for i in range(N-1):
    print((colors[i]))
# Original solution
import sys
n=int(eval(input()))
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=list(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)

# Optimized solution
import sys
sys.setrecursionlimit(10**6)
n=int(eval(input()))
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=list(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)
# Original solution
from collections import deque
from heapq import heappop
import sys
input = sys.stdin.readline
N = int(eval(input()))
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

d = max(D)
for M in [d, d+1]:
    flag = False
    Q = deque([argmax])
    check = [0]*N
    color = [2**M-1 for _ in range(N)]
    C = dict()
    while Q:
        v = Q.popleft()
        check[v] = 1
        for u in V[v]:
            if check[u]:
                continue
            else:
                Q.append(u)
            usable_colors = color[v] & color[u]
            if usable_colors == 0:
                flag = True
                break
            else:
                cnt = 0
                while usable_colors % 2 == 0:
                    usable_colors //= 2
                    cnt += 1

            C[tuple(sorted([u, v]))] = cnt
            color[v] -= 2**cnt
            color[u] -= 2**cnt
        if flag:
            break
    
    if M == d and flag == False:
        break

ans = [0]*(N-1)  
for i in range(N-1):
    ans[i] = C[T[i]]+1

print((max(ans)))
for i in range(N-1):
    print((ans[i]))

# Optimized solution
from collections import deque
import sys
input = sys.stdin.readline
N = int(eval(input()))
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

K = D[argmax]
Q = deque([])
C = dict()
for i, v in enumerate(V[argmax]):
    C[tuple(sorted([argmax, v]))] = i+1
    Q.append((v, i+1))

check = [0]*N
check[argmax] = 1
while Q:
    v, color = Q.popleft()
    check[v] = 1
    i = 0
    for u in V[v]:
        if check[u]:
            continue
        i += 1
        if i == color:
            i += 1
        C[tuple(sorted([u, v]))] = i
        Q.append((u, i))

print(K)
for i in range(N-1):
    print((C[T[i]]))
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(eval(input()))
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  svis = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  #print(x, viss)
  for y, i in e[x]:
    #print(x, y, t)
    while t in viss:
      t += 1
    if i in vis:
      continue
    #print(x, y, t)
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
    dfs(y)
  #print(res)
dfs(1)
print((max(res)))
for r in res: print(r)

# Optimized solution
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(eval(input()))
e = dd(list)
for i in range(N - 1):
  u, v = list(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])
  #print(x, vis)
  for y, i in e[x]:
    if res[i] > 0: continue
    while c in vis: c += 1
    #print(x, c)
    res[i] = c
    vis.add(c)
    dfs(y)
dfs(1)
print((max(res)))
for r in res: print(r)
# Original solution
# D - Coloring Edges on Tree

n = int(eval(input()))
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

# 2次元配列で塗る色（頂点,遷移先の頂点）を管理する
C = [[0]*n for _ in range(n)]

for _ in range(n-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print((max([len(d) for d in D])))

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[node][chi] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print((C[a][b]))

# Optimized solution
# D - Coloring Edges on Tree
import sys
sys.setrecursionlimit(10**6)

n = int(eval(input()))
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print((max([len(d) for d in D])))

C = {}

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[(node, chi)] = cid
            C[(chi, node)] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print((C[(a,b)]))
# Original solution
import sys
sys.setrecursionlimit(1000000)
 
n = int(eval(input()))
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = list(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(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)
 
dfs(0)
print((max(ans)))
for i in range(n-1):
  print((ans[i]))

# Optimized solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
g = [[] for _ in range(n)]
e = []
for i in range(n-1):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    e.append((a, b))

# topological順序の計算
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    x = s.pop()
    order.append(x)
    for nx in g[x]:
        if nx == parent[x]:
            continue
        parent[nx] = x
        s.append(nx)

color = [0]*n
for v in order:
    ng = color[v]
    c = 1
    for u in g[v]:
        if u == parent[v]:
            continue
        if c == ng:
            c += 1
        color[u] = c
        c += 1

ans = []
for a, b in e:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

print((len(set(ans))))
print(('\n'.join(map(str,ans))))
# Original solution
import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(eval(input()))
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in list(graph.items()):
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
que = deque()
color_dict = {i : set(range(1,1+_max)) for i in range(n)}
cur = _max_node
already = set()
while True:
    cnt = 1
    already.add(cur)
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            if _next not in already:
                que.append(_next)
                already.add(_next)
            candidate = color_dict[_next].intersection(color_dict[cur])
            cnt = list(candidate)[0]
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].remove(cnt)
            color_dict[_next].remove(cnt)
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print((colors[a][b]))

# Optimized solution
import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(eval(input()))
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in list(graph.items()):
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print((colors[a]))
    else:
        print((colors[b]))
# Original solution
import sys

input = sys.stdin.readline

N = int(eval(input()))

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = {color for color in range(1, k + 1)}
usedcolor = [None for _ in range(N)]
colored = {}

for v in range(N):
  unused_colors = colors - { usedcolor[v] }
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = unused_colors.pop()
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print((colored[(a, b)]))
  

# Optimized solution
import sys

input = sys.stdin.readline

N = int(eval(input()))

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [None for _ in range(N)]
colored = {}

def colors_except(x):
  for c in colors:
    if c == x:
      continue
    yield c

for v in range(N):
  unused_colors = colors_except(usedcolor[v])
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = next(unused_colors)
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print((colored[(a, b)]))
# Original solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]
ab = [[i] + LI() for i in range(n-1)]
col = [defaultdict(int) for _ in range(n)]
cnt = [0] * n
for i, a, b in ab:
    edges[a-1].append((i, b-1))
    edges[b-1].append((i, a-1))
    cnt[a-1] += 1
    cnt[b-1] += 1

k = max(cnt)
print(k)
used_edge = [False] * n
que = deque([(0, -1)])
edges_color = [None] * (n-1)
while que:
    v, p = que.popleft()
    for i, u in edges[v]:
        if used_edge[i]:
            continue
        if u == p:
            continue
        cnt = 1
        while col[u][cnt] or col[v][cnt]:
            cnt += 1
        col[u][cnt] = 1
        col[v][cnt] = 1
        edges_color[i] = cnt
        used_edge[i] = False
        que.append((u, v))
for c in edges_color:
    print(c)

# Optimized solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]
ab = [[i] + LI() for i in range(n-1)]
cnt = [0] * n
for i, a, b in ab:
    edges[a-1].append((i, b-1))
    edges[b-1].append((i, a-1))
    cnt[a-1] += 1
    cnt[b-1] += 1

k = max(cnt)
print(k)
que = deque([(0, -1, 0)])
edges_color = [None] * (n-1)
while que:
    v, p, col = que.popleft()
    cnt = 1
    for i, u in edges[v]:
        if edges_color[i] != None:
            continue
        if u == p:
            continue
        if cnt != col:
            edges_color[i] = cnt
        else:
            edges_color[i] = cnt + 1
            cnt += 1
        que.append((u, v, cnt))
        cnt += 1
for c in edges_color:
    print(c)
# Original solution
import sys
import math

def func(s):
    return int(s)-1


N=int(eval(input()))
e=[list(map(func,input().split()))+[i] for i in range(N-1)]
e.sort()

x=[0 for i in range(N)]
for i in range(N-1):
    x[e[i][0]]+=1
    x[e[i][1]]+=1
print((max(x)))

e2=[[0 for j in range(x[i])]for i in range(N)]
ans=[0 for i in range(N-1)]

for i in range(N-1):
    [p,q,r]=e[i]
    for j in range(x[p]):
        if e2[p][j]==0:
            e2[p][j]=1
            if j<x[q]: e2[q][j]=1
            ans[r]=j
            break
        
for i in range(N-1):
    print((ans[i]+1))



# Optimized solution
import sys
import math

def func(s):
    return int(s)-1


N=int(eval(input()))
e=[list(map(func,input().split()))+[i] for i in range(N-1)]
e.sort()

x=[0 for i in range(N)]
for i in range(N-1):
    x[e[i][0]]+=1
    x[e[i][1]]+=1
print((max(x)))

e2=[[0 for j in range(x[i])]for i in range(N)]
ans=[0 for i in range(N-1)]

y=[0 for i in range(N)]

for i in range(N-1):
    [p,q,r]=e[i]

    e2[p][y[p]]=1
    if y[p]<x[q]: e2[q][y[p]]=1
    ans[r]=y[p]

    for j in range(y[p],x[p]):
        if e2[p][j]==0:
            y[p]=j
            break
    for j in range(y[q],x[q]):
        if e2[q][j]==0:
            y[q]=j
            break

for i in range(N-1):
    print((ans[i]+1))
# Original solution
from collections import deque
n = int(eval(input()))
edges = {}
lst = [set()for i in range(n)]
vert = [set() for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = list(map(int,input().split()))
    lst[a-1].add(b)
    lst[b-1].add(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    while lst[x-1]:
        i = lst[x-1].pop()
        lst[i-1].discard(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].add(j)
                vert[i-1].add(j)
                ans[edges[(a,b)]] = j
                break
print((max(ans)))
for i in range(len(ans)):
    print((ans[i]))


# Optimized solution
n = int(eval(input()))
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = list(map(int,input().split()))
    graph[a].append((i,b))
    graph[b].append((i,a))
colors = [0 for _ in range(n)]
parents = [0]*(n+1)
stack = [(1,0)]
while stack:
    x,c = stack.pop()
    color = 1
    for i,y in graph[x]:
        if parents[x] == y:
            continue
        else:
            parents[y] = x
            if color == c:
                color += 1
            colors[i] = color
            stack.append((y,color))
            color += 1
print((max(colors)))
for i in range(1,n):
    print((colors[i]))
# Original solution
from collections import deque
N = int(eval(input()))
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
watch = [0]*N
watch[0] = 1
for i in range(N-1):
    a,b = list(map(int,input().split()))
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if watch[next] == 0:
                queue.append(next)
                watch[next] = 1

for i in ans:
    print(i)

# Optimized solution
from collections import deque
N = int(eval(input()))
node = [[]for i in range(N)]
side = []
count = [0]*N
ans = [0]*(N-1)
closed = [0]*N
for i in range(N-1):
    a,b = list(map(int,input().split()))
    side.append([a-1, b-1])
    node[a-1].append(i)
    node[b-1].append(i)
    count[a-1] += 1
    count[b-1] += 1

K = max(count)
print(K)

queue = deque([[0,K+1]])


while queue:
    q,m = queue.popleft()
    p = 1
    for i in node[q]:
        if p == m:
            p += 1
        if ans[i] == 0:
            ans[i] = p
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if closed[next] == 0:
                queue.append([next,p])
                closed[next] = 1
            p += 1

for i in ans:
    print(i)