CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

def main():
    N = int(eval(input()))
    sides = [[] for _ in range(N-1)]
    
    for i in range(N-1):
        a,b = list(map(int, input().split()))
        sides[a-1].append((b-1,i))

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

    print((max(ans)))
    for color in ans:
        print(color)


if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

def main():
    N = int(eval(input()))
    sides = [[] for _ in range(N-1)]
    
    for i in range(N-1):
        a,b = list(map(int, input().split()))
        sides[a-1].append((b-1,i))

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        if focus == N-1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            # if child < N-1:
            #     dfs(child,color)
            dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

    print((max(ans))) 
    for color in ans:
        print(color)


if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
degree = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_color = [0 for i in range(n)]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append([b,i])
    degree[a] += 1
    degree[b] += 1


maxcolor = max(degree)
search_list = [0]
node_color[0] = 0

while search_list:
    new_search_list = []
    for i in search_list:
        if node_color[i] == 0:
            color_list = [ k for k in range(1,maxcolor+1) ]
        else:
            color_list = [ k for k in range(1,maxcolor+1) if k != node_color[i] ]
        p = 0
        for j, v in enumerate(connect_list[i]):
            a, b = v
            new_search_list.append(a)
            node_color[a] = color_list[p]
            connect_list[i][j] = [b,color_list[p]]
            p += 1
    search_list = new_search_list

ans_list = []
for i in connect_list:
    for j in i:
        ans_list.append(j)

ans_list.sort()
print(maxcolor)
for i in ans_list:
    print((i[1]))

# Optimized solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
degree = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_color = [0 for i in range(n)]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append([b,i])
    degree[a] += 1
    degree[b] += 1


maxcolor = max(degree)
search_list = [0]
node_color[0] = 0
color_list = [ k for k in range(1,maxcolor+1) ]

while search_list:
    new_search_list = []
    for i in search_list:
        p = 0
        for j, v in enumerate(connect_list[i]):
            a, b = v
            new_search_list.append(a)
            if node_color[i] == color_list[p]:
                p += 1
            node_color[a] = color_list[p]
            connect_list[i][j] = [b,color_list[p]]
            p += 1
    search_list = new_search_list

ans_list = []
for i in connect_list:
    for j in i:
        ans_list.append(j)

ans_list.sort()
print(maxcolor)
for i in ans_list:
    print((i[1]))
# Original solution
import sys
from collections import deque
input = sys.stdin.readline
N = int(eval(input()))
D = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = tuple([int(x) for x in input().strip().split()])
    AB[n] = (a, b)
    D[a-1][b-1] = '#'
    D[b-1][a-1] = '#'

maxc = 0

for i, d in enumerate(D):
    c = d.count('#')
    if c > maxc:
        maxc = c
        maxi = i

q = deque([])
c = 1
for i in range(N):
    if D[maxi][i] == '#':
        D[maxi][i] = c
        D[i][maxi] = c
        c += 1
        q.append(i)

while q:
    ind = q.popleft()
    c = 1
    for i in range(N):
        while c in D[ind]:
            c += 1
        if D[ind][i] == '#':
            D[ind][i] = c
            D[i][ind] = c
            c += 1
            if i not in q:
                q.append(i)

print(maxc)
for a, b in AB:
    print((D[a-1][b-1]))


# Optimized solution
import sys
from collections import deque
input = sys.stdin.readline
N = int(eval(input()))
D = [deque([]) for _ in range(N)]
MAP = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a, b)
    D[a-1].append(b-1)
    D[b-1].append(a-1)

maxc = 0

for i, d in enumerate(D):
    c = len(d)
    if c > maxc:
        maxc = c
        maxi = i

C = [[0] * maxc for _ in range(N)]
for n in D[maxi]:
    #print('max index = {}, next node = {}'.format(maxi, n))
    MAP[maxi][n] = c
    MAP[n][maxi] = c
    C[maxi][c-1] = 1
    C[n][c-1] = 1
    c += 1

print(maxc)
for a, b in AB:
    if a-1 == maxi or b-1 == maxi:
        print((MAP[a-1][b-1]))
    for i in range(maxc):
        if C[a-1][i] == 0 and C[b-1][i] == 0:
            print((i+1))
            C[a-1][i] = 1
            C[b-1][i] = 1
            break
# Original solution
import sys
from collections import deque
input = sys.stdin.readline
N = int(eval(input()))
D = [deque([]) for _ in range(N)]
MAP = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a, b)
    D[a-1].append(b-1)
    D[b-1].append(a-1)

maxc = 0

for i, d in enumerate(D):
    c = len(d)
    if c > maxc:
        maxc = c
        maxi = i

C = [[0] * maxc for _ in range(N)]
for n in D[maxi]:
    #print('max index = {}, next node = {}'.format(maxi, n))
    MAP[maxi][n] = c
    MAP[n][maxi] = c
    C[maxi][c-1] = 1
    C[n][c-1] = 1
    c += 1

print(maxc)
for a, b in AB:
    if a-1 == maxi or b-1 == maxi:
        print((MAP[a-1][b-1]))
    for i in range(maxc):
        if C[a-1][i] == 0 and C[b-1][i] == 0:
            print((i+1))
            C[a-1][i] = 1
            C[b-1][i] = 1
            break

# Optimized solution
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(eval(input()))
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

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

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print((dic[ab]))
# Original solution
from collections import deque
import sys
input = sys.stdin.readline
n = int(eval(input()))
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = list(map(int,input().split()))
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [set(range(1,m+1)) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      cu = (g2[cur]&g2[i]).pop()
      g2[cur].discard(cu)
      g2[i].discard(cu)
      d[(min(cur,i),max(cur,i))] = cu
for i in l:
  print((d[i]))


# Optimized solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = list(map(int,input().split()))
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print((d[i]))
# Original solution
from collections import deque
def main():
    n = int(eval(input()))
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int,input().split()))
        ab.append([a-1, b-1])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0]=0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print((max(visit)))
    for a, b in ab:
        print((visit[b]))

if __name__=="__main__":
    main()

# Optimized solution
from collections import deque
def main():
    n = int(eval(input()))
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = list(map(int,input().split()))
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print((max(visit)))
    for a, b in ab:
        print((visit[b]))

if __name__=="__main__":
    main()
# Original solution
import sys
sys.setrecursionlimit(4100000)
N = int(eval(input()))
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = list(map(int,input().split(' ')))
    tree[a].append([b,i])

last_color = 0
bfs_use_coler = [[] for _ in range(N+1)]

def solve(n,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    for val in tree[n]:
        if already_make[val[1]] != -1:
            continue
        use_coloer = -1
        length = last_color+1
        a_tree = list(set(list(range(1,length))) - set(bfs_use_coler[val[0]]) )
        b_tree = list(set(list(range(1,length)))  - set(bfs_use_coler[n])) 
        ab_tree = list(set(a_tree)& set(b_tree))
        '''
        for i in range(1,length):
            if i in bfs_use_coler[val[0]] or i in bfs_use_coler[n]:
                continue
            else:
                use_coloer = i
                break
        if use_coloer == -1:
            last_color +=1
            use_coloer = last_color
        '''
        if len(ab_tree) > 0:
            use_coloer = ab_tree[0]
        else:
            last_color +=1
            use_coloer = last_color
        bfs_use_coler[val[0]].append(use_coloer)
        bfs_use_coler[n].append(use_coloer)
        already_make[val[1]] = use_coloer
    return last_color

for i in range(1,N+1):
    last_color = solve(i,last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)



# Optimized solution
import sys
sys.setrecursionlimit(4100000)
N = int(eval(input()))
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = list(map(int,input().split(' ')))
    tree[a].append([b,i])

last_color = 0
#bfs_use_coler = [[ -1 for _ in range(N+1) ] for _ in range(N+1) ] 

def solve_bfs(previous_colors,n_list,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    next_colors = []
    next_n_list =[]
    for idx1,n in enumerate(n_list):
        use_color_num = 1
        for idx2,val in enumerate(tree[n]):
            if use_color_num == previous_colors[idx1]:
                use_color_num += 1
            already_make[val[1]] = use_color_num
            next_colors.append(use_color_num)
            next_n_list.append(val[0])
            last_color = max(use_color_num,last_color)
            use_color_num += 1
    if len(next_colors) > 0:
        return solve_bfs(next_colors,next_n_list,last_color)
    else:
        return last_color

last_color = solve_bfs([0],[1],last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(min(a,b),max(a,b))]=i
    ans=[None]*(n-1)

    def dfs(v=0,p=-1,c=0):
        col=1
        for nv in E[v]:
            col+=col==c
            if(nv==p): continue
            ans[idx[(min(v,nv),max(v,nv))]]=col
            dfs(nv,v,col)
            col+=1
    dfs()
    print(max(ans))
    print(*ans,sep='\n')
resolve()


# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(a,b)]=i
        idx[(b,a)]=i

    k=max(len(E[i]) for i in range(n))
    # dfs
    ans=[None]*(n-1)
    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        # 根のとき -> 辺を張る
        if(p==-1):
            col=1
            for nv in E[v]:
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))
        # そうでないとき -> 親の色は除外
        else:
            col=1
            for nv in E[v]:
                if(nv==p): continue
                col+=(col==ans[idx[(v,p)]]) # 親の色になってしまったら足す
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))

    print(k)
    print(*ans,sep='\n')
resolve()
# Original solution
from collections import Counter, defaultdict
from queue import Queue
G = defaultdict(list)

C = Counter()
N = int(eval(input()))
ans = {}
o = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

cs = [0] * (N+1)
def bfs(v):
    ret = 0
    visited = set()
    q = Queue()
    visited.add(v)
    q.put(v)
    while not q.empty():
        v = q.get()
        counter = 1
        for c in G[v]:
            if not c in visited:
                visited.add(c)
                if counter == cs[v]:
                    counter += 1
                cs[c] = ans[(c,v)] = ans[(v,c)] = counter
                counter += 1
                q.put(c)

bfs(1)
print((C.most_common(1)[0][1]))
for a,b in o:
    print((ans[(a,b)]))

# Optimized solution
from collections import Counter, defaultdict
from sys import getrecursionlimit,setrecursionlimit
setrecursionlimit(100*getrecursionlimit())
G = defaultdict(list)
C = Counter()
N = int(eval(input()))
ans = {}
o = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

a = C.most_common(1)[0][0]
b = C.most_common(1)[0][1]

visited = [False] * (N+1)
def dfs(v, p):
    visited[v] = True
    counter = 1
    for c in G[v]:
        if not visited[c]:
            if p != 0 and counter == ans[(v, p)]:
                counter += 1
            ans[(v, c)] = ans[(c, v)] = counter
            counter += 1
            dfs(c, v)

dfs(a, 0)

print(b)
for a,b in o:
    print((ans[(a,b)]))
# Original solution
# -*- coding: utf-8 -*-

from collections import deque

n = int(eval(input()))
edges = [list(map(int, input().split())) for i in range(n-1)]

# 使われていない色を保持する
nodes = [deque([i for i in range(1, n)]) for j in range(n)]

tree = {}
for edge in sorted(edges):
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b

    color = nodes[a-1].popleft()
    tree[(a, b)] = color
    nodes[b-1].remove(color)

print((max(tree.values())))
for edge in edges:
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b
    print((tree[(a, b)]))

# Optimized solution
# -*- coding: utf-8 -*-

from collections import deque

n = int(eval(input()))
edges = [list(map(int, input().split())) for i in range(n-1)]

tree = {}
node_in = [0 for i in range(n)] # 頂点に入る辺は1つ
node_out = [[0] for i in range(n)] # 頂点から出る辺は1つ以上
for edge in sorted(edges):
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b

    color = 0
    if node_out[a-1][-1] == 0:
        if node_in[a-1] <= 1: # node_in[a-1] == 0の時1、1の時2なのでまとめて
            color = node_in[a-1] + 1
        else: # node_in[a-1] >= 2
            color = 1
    else:
        color = node_out[a-1][-1] + 1
        if node_in[a-1] == color:
            color += 1
            
    tree[(a, b)] = color
    node_out[a-1].append(color)
    node_in[b-1] = color

print((max(tree.values())))
for edge in edges:
    a = edge[0] # 頂点a
    b = edge[1] # 頂点b
    print((tree[(a, b)]))
# Original solution
n=int(eval(input()))
l=[list(map(int,input().split()))+[i] for i in range(n-1)]
l.sort()
#print(l)
aa=[[] for _ in range(n)]
#aa[l[0][0]-1].append(1)
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    #print(d,q)
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    for k in range(1,n):
                        if k not in set(aa[i]) and k not in set(aa[j]):
                            aa[j].append(k)
                            aa[i].append(k)
                            break
        q=q1
        c+=1
        #print(aa,d,q)
    return d


pt=[[] for _ in range(n)]
for i in range(n-1):
    pt[l[i][0]-1].append(l[i][1]-1)
    pt[l[i][1]-1].append(l[i][0]-1)
#print(pt)
ans=bfs(l[0][0]-1)
#print(aa)
A=0
for i in range(n):
    A=max(A,max(aa[i]))
print(A)
for i in range(n-1):
    #print(aa)
    #print(aa[l[i][0]-1][0])
    l[i].append(aa[l[i][0]-1][0])
    aa[l[i][0]-1]=aa[l[i][0]-1][1:]
    aa[l[i][1]-1]=aa[l[i][1]-1][1:]
l=sorted(l, key=lambda x: x[2])
for i in range(n-1):
    print((l[i][3]))


# Optimized solution
n = int(eval(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)]
#print(l)
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(flg,ans)
print((max(flg)))
for i in range(1,n):
    print((ans[i]))
# Original solution
N=int(eval(input()))
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[set(i for i in range(1,N+1)) for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = graph[i]&graph[j]
    a_list.append(min(ans))
    graph[i].remove(min(ans))
    graph[j].remove(min(ans))
print((max(a_list)))
for i in a_list:
    print(i)


# Optimized solution
N=int(eval(input()))
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    tmp=min(ans)
    a_list.append(tmp)
    graph[i].remove(tmp)
    graph[j].remove(tmp)
print((max(a_list)))
for i in a_list:
    print(i)
# Original solution
N=int(eval(input()))
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    tmp=min(ans)
    a_list.append(tmp)
    graph[i][tmp-1]=N+1
    graph[j][tmp-1]=N+1
print((max(a_list)))
for i in a_list:
    print(i)


# Optimized solution
import sys
sys.setrecursionlimit(500000)
N = int(eval(input()))
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = list(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)
# Original solution
import sys

sys.setrecursionlimit(10**6)
N = int(eval(input()))
P = [[] for _ in range(N + 1)]
P2 = [[0] * (N + 1) for _ in range(N + 1)]
AB = []
for _ in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    P[a].append(b)
    P[b].append(a)
    AB.append((a,b))
C = 0

for p in P:
    if len(p) > C:
        C = len(p)


def f(n, pre, used):
    c = 1
    for i, next_n in enumerate(P[n]):
        if pre == next_n: continue
        if c == used: c += 1
        P2[n][next_n] = c
        P2[next_n][n] = c
        f(next_n, n, c)
        c += 1


print(C)
f(1, -1, 0)
# print(P2)
for a,b in AB:
    print((P2[a][b]))


# Optimized solution
import sys
sys.setrecursionlimit(10**6)
N = int(eval(input()))
P = [[] for _ in range(N + 1)]
AB = []
for _ in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    P[a].append(b)
    P[b].append(a)
    AB.append((a,b))
C = 0

for p in P:
    if len(p) > C:
        C = len(p)


P2 = dict()
def f(n, pre, used):
    c = 1
    for i, next_n in enumerate(P[n]):
        if pre == next_n: continue
        if c == used: c += 1
        # P2[n][next_n] = c
        # P2[next_n][n] = c
        if n > next_n:
            a, b = next_n, n
        else:
            b,a = next_n, n
        P2[(a,b)] = c
        f(next_n, n, c)
        c += 1


print(C)
f(1, -1, 0)
for ab in AB:
    print((P2[ab]))
# Original solution
'''catupper

'''

import sys
sys.setrecursionlimit(1000000)#DFSは再帰の上限回数に注意

n = int(eval(input()))
edge = [[] for i in range(n)]
a = [0] * n#頂点を格納しておく配列
b = [0] * n

color_dict = {}#色を覚えておく
k = 0

def dfs(x, last = -1, ban_color = -1):
#lastは、どこから来たか、逆走を防ぐ。使っちゃいけない色も引数
    global k#グローバル変数
    color = 1
    for to in edge[x]:
        if to == last:continue
        #来た頂点に戻ろうとしたら、何もしない
        if color == ban_color:color += 1
        #使っちゃいけない色なら、新しい色にする
        color_dict[(x, to)] = color
        dfs(to, x, color)
        #次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1#色を新しくする
    k = max(k, color-1)#何色を使ったか、覚えておく

for i in range(n-1):
    a[i], b[i] = list(map(int, input().split()))
    a[i] -= 1#0-indexにする
    b[i] -= 1
    edge[a[i]].append(b[i])#無向グラフ
    edge[b[i]].append(a[i])

dfs(0)#最初の頂点をDFSに入れてスタート
print(k)#まず、何色必要かを出力

for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    if (a[i], b[i]) in color_dict:#辞書から答を出力
        print((color_dict[(a[i], b[i])]))
    else:
        print((color_dict[(b[i], a[i])]))

# Optimized solution
'''catupper
ポイントA.再帰DFSを使う。
ポイントB.入力に注意。
辺は頂点を結ぶので(a[i], b[i])で表現され、対応する色を
color_dict[(a[i], b[i])]としている。
配列が二重配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):    if (a[i], b[i]) in color_dict:
'''

import sys
sys.setrecursionlimit(1000000)#DFSは再帰の上限回数に注意

n = int(eval(input()))
edge = [[] for i in range(n)]
#どの頂点とどの頂点が繋がっているかを格納しておく配列
a = [0] * n#頂点aに繋がっている頂点bの番号を格納しておく配列
b = [0] * n

color_dict = {}#色を覚えておく
k = 0

def dfs(x, last = -1, ban_color = -1):
#lastは、どこから来たか、逆走を防ぐ。使っちゃいけない色も引数
    global k#グローバル変数
    color = 1
    for to in edge[x]:
    #配列edgeに格納されている次の頂点toを順番にチェック
        if to == last:continue
        #来た頂点に戻ろうとしたら、何もしない
        if color == ban_color:color += 1
        #使っちゃいけない色なら、新しい色にする
        color_dict[(x, to)] = color
        dfs(to, x, color)
        #次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1#色を新しくする
    k = max(k, color-1)#何色を使ったか、覚えておく

for i in range(n-1):
    a[i], b[i] = list(map(int, input().split()))
    a[i] -= 1#0-indexにする
    b[i] -= 1
    edge[a[i]].append(b[i])#無向グラフ
    edge[b[i]].append(a[i])

dfs(0)#最初の頂点をDFSに入れてスタート
#print(color_dict)

print(k)#まず、何色必要かを出力

for i in range(n-1):#辺の色を1から頂点番号-1まで出力
    print((color_dict[(a[i], b[i])]))
'''  
    if (a[i], b[i]) in color_dict:#辞書から答を出力
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])
'''