Problem:
 Score : 400 points    Problem Statement  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 1 3
1 2
2 3      Sample Output 1 2
1
2       Sample Input 2 8
1 2
2 3
2 4
2 5
4 7
5 6
6 8      Sample Output 2 4
1
2
3
4
1
1
2       Sample Input 3 6
1 2
1 3
1 4
1 5
1 6      Sample Output 3 5
1
2
3
4
5

Solution (Python):
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)

Solution (Python):
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=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()
print("\n".join(map(str, Ans)))

Solution (Python):

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)

Solution (Python):

from collections import deque

n = int(input())

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

ver = [[] for i in range(n)]

for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)



color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1



while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1



k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])

Solution (Python):
from collections import deque
n = int(input())
g = [[] for _ in range(n)]
ab = []

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

q = deque([0])
par = [0] * n
order = []

while q:
    x = q.pop()
    order.append(x)
    for y in g[x]:
        if y == par[x]:
            continue
        par[y] = x
        q.append(y)

color = [-1] * n
for x in order:
    ng = color[x]
    c = 1
    for y in g[x]:
        if y == par[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

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

k = max(ans)
print(k)
print("\n".join(map(str, ans)))

Solution (Python):
from collections import deque
from heapq import heappush, heappop
n = int(input()) 



graph = [[] for _ in range(n)]
edge = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edge[(a, b)] = i
    edge[(b, a)] = i

def bfs(graph, start, n):
    visited = [-1] * n
    que = deque()
    color = [0] * (n - 1)
    visited[start] = 0
    que.append(start)
    while que:
        node = que.popleft()
        c = 1
        for e in graph[node]:
            if visited[e] < 0:
                if visited[node] == c:
                    c += 1
                visited[e] = c
                color[edge[(e, node)]] = c
                que.append(e)
                c += 1
    return color

r = bfs(graph, 0, n)
ans = max(r)
print(ans)
for k in r:
    print(k)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
g = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]

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)


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, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Solution (Python):
def mxmi(a,b):
    if a<b:
        return a,b
    else:
        return b,a
from collections import deque
n = int(input())
tree = [[] for i in range(n)]
color = [0]*(n-1)
d = dict()
for i in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    d[(a-1,b-1)] = i
ans = 0
q = deque([(0,0,0)])
while q:
    cnt = 0
    f = 1
    now,prev,col = q.popleft()
    for node in tree[now]:
        cnt+=1
        if node !=prev:
            if f==col:f+=1
            q.append((node,now,f))
            a,b = mxmi(now,node)
            color[d[(a,b)]] = f
            f+=1
    ans = max(ans,cnt)


ls = list(d.items())
ls.sort(key=lambda x:x[1])
print(ans)
for i in range(n-1):
    print(color[i])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N-1)]
graph = defaultdict(list)
edge = defaultdict(int)

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

K = 0

for v in graph.values():
    K = max(K, len(v))


color = list(range(1, K + 1))

q = deque()
q.append((0, None))
while q:
    i, color_from = q.popleft()
    tmp = -1
    
    for node in graph[i]:
        str_ = "{},{}".format(i, node)
        
        if not edge[str_]:
            use_color = color[tmp]
            if use_color == color_from:
                
                tmp -= 1
                use_color = color[tmp]
            
            tmp -= 1
            edge[str_] = use_color
            edge["{},{}".format(node, i)] = use_color
            q.append((node, use_color))
print(K)
for a, b in L:
    print(edge["{},{}".format(a-1, b-1)])

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)

N = int(input())
li = [0]*(N-1)
dic = {}
graph = [[]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a,b = inputlist()
    if a >= b:
        a,b = b,a
    graph[a].append(b)
    graph[b].append(a)
    k = tuple([a,b])
    dic[k] = i
ans = 0
indexa = -1
seen = [False]*(N+1)
for i in range(1,N+1):
    k = len(graph[i])
    if k > ans:
        indexa = i
    ans = max(ans,k)
def dfs(i,v):
    for v1 in graph[v]:
        if seen[v1]:
            continue
        seen[v1] = True
        i +=1
        i %= ans
        aa = min(v,v1)
        bb = max(v,v1)
        ka = tuple([aa,bb])
        li[dic[ka]] = i
        dfs(i,v1)
dfs(-1,indexa)
print(ans)
for i in range(N-1):
    print(li[i]+1)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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


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

for _ in range(n-1):
    a, b = 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)])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        while(cnt in s[v]):
                cnt+=1
        s[v].add(cnt)
        s[nv].add(cnt)
        dic[tuple(sorted([v,nv]))]=cnt
        dfs(G,nv,v,cnt)
        
N=int(input())
G=[[] for i in range(N)]
e=[]
s=[set() for i in range(N)]
dic={}
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append(sorted([a,b]))
l=0
for i in range(N):
    l=max(l,len(G[i]))
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    print(dic[e[i][0],e[i][1]])

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**8)

N = int(input())
li = [0]*(N-1)
dic = {}
graph = [[]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a,b = inputlist()
    if a >= b:
        a,b = b,a
    graph[a].append(b)
    graph[b].append(a)
    k = tuple([a,b])
    dic[k] = i
ans = 0
indexa = -1
seen = [False]*(N+1)
for i in range(1,N+1):
    k = len(graph[i])
    if k > ans:
        indexa = i
    ans = max(ans,k)
def dfs(i,v):
    for v1 in graph[v]:
        if seen[v1]:
            continue
        seen[v1] = True
        i +=1
        i %= ans
        aa = min(v,v1)
        bb = max(v,v1)
        ka = tuple([aa,bb])
        li[dic[ka]] = i
        dfs(i,v1)
dfs(-1,indexa)
print(ans)
for i in range(N-1):
    print(li[i]+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dic[str(v)+'t'+str(nv)]=cnt
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dic={}
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    if str(e[i][0])+'t'+str(e[i][1]) in dic:
        print(dic[str(e[i][0])+'t'+str(e[i][1])])
    else:
        print(dic[str(e[i][1])+'t'+str(e[i][0])])

Solution (Python):
N = int(input())
vert = [0 for _ in range(N - 1)]
D = {}
E = {i: [i] for i in range(N)}
F = {i: [] for i in range(N)}
for i in range(N - 1):
  a, b = map(int, input().split())
  D[(a-1)*N+b-1], D[(b-1)*N+a-1] = i, i
  E[a-1].append(b-1)
  E[a-1][0] += N
  E[b-1].append(a-1)
  E[b-1][0] += N
m = max(E[i][0] for i in E)
K = m // N
par = [-1 for _ in range(N)]
root = m % N
par[root] = N + 1
p = [root]
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in range(1, E[p[i]][0] // N + 1):
      tmp = E[p[i]][j]
      if par[tmp] == -1:
        par[tmp] = p[i]
        F[p[i]].append(tmp)
        cnt += 1
        p.append(tmp)
  pnt = n
q = [root]
t = 1
m = -1
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    t = 1
    if par[q[i]] != N + 1:
      m = vert[D[q[i]*N+par[q[i]]]]
    for j in F[q[i]]:
      if t == m:
        t += 1
      vert[D[j*N+q[i]]] = t
      q.append(j)
      t += 1
      cnt += 1
  pnt = n
print(K)
for i in range(N-1):
  print(vert[i])

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = mylistinput(n-1)

g = [ [] for _ in range(n) ]
for i in range(n-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)


color = [-1] * n

def bfs(g):
    used_color = [ [-1] ]*n
    q = deque()
    q.append([0,0])
    while q:
        tmp = q.popleft()
        v = tmp[0]
        c = tmp[1]
        color[v] = c
        ls_nc = list(reversed(list(range(1,len(g[v])+1))))
        if c==0:
            pass
        elif c in ls_nc:
            ls_nc.remove(c)
        else:
            pass
        for nv in g[v]:
            if color[nv]!=-1:
                pass
            else:
                nc = ls_nc.pop()
                q.append([nv,nc])
    return True

if bfs(g):
    print(max(color))
    for i in range(n-1):
        b = ab[i][1] - 1
        print(color[b])
else:
    print("Error")

Solution (Python):
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for node in path[pre]:
            if visited[node]:
                continue
            if c == k:
                k += 1
            visited[node] = True
            ans[(pre, node)] = k
            que.append((node, k))
            k += 1

    print(max(ans.values()))
    print('\n'.join([str(ans[key]) for key in ab]))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            
            if c == k:
                k += 1
            visited[next_node] = True
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            k += 1
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            
            if c == k:
                k += 1
            visited[next_node] = True
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            k += 1
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
        
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        
        k = 0
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            k += 1
            if c == k:
                k += 1
            visited[next_node] = True
            
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = {}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append((a,b))
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[tuple(sorted((p,i)))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color.values()))
for i in ab:
  print(color[i])

Solution (Python):
import sys
input=sys.stdin.readline
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))
check=[False]*n
p=0
stack=[(0,0)]
ans=[0]*(n-1)
while len(stack)>0:
    now=stack.pop()
    x=now[0]
    y=now[1]
    check[x]=True
    if len(G[x])>p:
        p=len(G[x])
    j=1
    for i in G[x]:
        if check[i[0]]:
            continue
        if j==y:
            j+=1
        ans[i[1]]=j
        stack.append((i[0],j))
        j+=1
print(p)
for i in ans:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
es=[[] for i in range(n)]
l=[list(map(int,input().split())) for i in range(n-1)]
for i in range(n-1):
   l[i][0]-=1
   l[i][1]-=1
   es[l[i][0]].append(l[i][1])
   es[l[i][1]].append(l[i][0])
dic={}
use=[1]*n
def dfs(v,k):
    cnt=0
    use[v]=0
    for i in es[v]:
        if use[i]:
            if cnt==k:
                cnt+=1
            dic[(min(v,i),max(v,i))]=cnt
            dfs(i,cnt)
            cnt+=1
dfs(0,-1)
ans=[0]*(n-1)
k=0
for i in range(n-1):
    ans[i]=dic[l[i][0],l[i][1]]+1
    k=max(k,ans[i])
print(k)
for i in ans:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
es=[[] for i in range(n)]
l=[list(map(int,input().split())) for i in range(n-1)]
for i in range(n-1):
   l[i][0]-=1
   l[i][1]-=1
   l[i][0],l[i][1]=min(l[i][0],l[i][1]),max(l[i][0],l[i][1])
   es[l[i][0]].append(l[i][1])
   es[l[i][1]].append(l[i][0])
dic={}
use=[1]*n
def dfs(v,k):
    cnt=0
    use[v]=0
    for i in es[v]:
        if use[i]:
            if cnt==k:
                cnt+=1
            dic[(min(v,i),max(v,i))]=cnt
            dfs(i,cnt)
            cnt+=1
dfs(0,-1)
ans=[0]*(n-1)
k=0
for i in range(n-1):
    ans[i]=dic[l[i][0],l[i][1]]+1
    k=max(k,ans[i])
print(k)
for i in ans:
    print(i)

Solution (Python):
import sys
from collections import deque, defaultdict
def input() : return sys.stdin.readline().strip()

def main():
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    to = [[] for i in range(N)]

    for edge in edges:
        a, b = edge
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    colors = defaultdict(int)
    def bfs():
        q = deque() 
        q.append((0, 0))
        while len(q):
            now, par_col = q.popleft()
            color = 0
            for v in to[now]:
                x, y = sorted([v, now])
                if colors[(x, y)]:
                    continue
                else:
                    color += 1
                    if color == par_col:
                        color += 1

                    colors[(x, y)] = color
                    q.append((v, color))
    bfs()

    ans = max(colors.values())
    print(ans)
    
    for edge in edges:
        x, y = edge
        x -= 1
        y -= 1
        print(colors[(x, y)])

                


        



if __name__ == "__main__":
    main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


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


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
edges = list(
    map(lambda s: 
        tuple(map(int,s.strip().split())), sys.stdin.readlines()
    )
)

children = [ [] for _ in range(n+1)]
for e in edges:
    children[e[0]].append(e[1])
    children[e[1]].append(e[0])

colors = [{} for _ in range(n+1)]

check = [False for _ in range(n+1)]

que = deque()
que.append((1, 0))

def solve(i, x):
    
    check[i] = True

    color = 0
    for node in children[i]:
        if check[node]:
            continue

        color += 1
        if color == x:
            color += 1

        
        colors[i][node] = color
        colors[node][i] = color
        que.append((node, color))

while que:
    e = que.popleft()
    solve(e[0], e[1])

maxColor = 0

for i in range(1, n+1):
    c = colors[i]
    maxColor = max(maxColor, max(c.values()))

print(maxColor)

for e in edges:
    print(colors[e[0]][e[1]])

Solution (Python):
n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append((b-1, i))
  adj[b-1].append((a-1, i))
max_degree = 0
for i in range(n):
  degree = len(adj[i])
  if degree > max_degree:
    root = i
    max_degree = degree
color = [[] for _ in range(n)]
edge = [0] * (n - 1)
queue = [root]
parent = [root] * n
while queue:
  vertex = queue.pop()
  c = 1
  for v, i in adj[vertex]:
    if parent[vertex] == v:
      continue
    while c in color[v] or c in color[vertex]:
      c += 1
    color[v].append(c)
    color[vertex].append(c)
    edge[i] = c
    queue.append(v)
    parent[v] = vertex
    c += 1
print(max_degree)
for c in edge:
  print(c)

Solution (Python):
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  N = int(readline())
  graph = [[] for _ in range(N+1)]
  m = map(int, read().split())
  AB = list(zip(m,m))
  
  for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
  
  root = 1
  parent = [0] *(N+1)
  order = []
  stack = [root]
  Q = deque(stack)
  while Q:
    x = Q.popleft()
    order.append(x)
    for y in graph[x]:
      if y == parent[x]:
        continue
      parent[y] = x
      Q.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
  ans = []
  for a, b in AB:
    if parent[a] == b:
      ans.append(color[a])
    else:
      ans.append(color[b])
  K = max(ans)
  print(K)
  print('\n'.join(map(str, ans)))
  
  
  
if __name__ == '__main__':
  main()

Solution (Python):
from collections import deque

N = int(input())
edges = {i: [] for i in range(N)}
edgeind = {}
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
    edgeind[(a - 1, b - 1)] = i


K = 0
root = -1
for i in range(N):
    K = max(K, len(edges[i]))
    if K == len(edges[i]):
        root = i


que = deque()
que.append((root, -1, -1))  
ans = [-1 for i in range(N - 1)]

while len(que) > 0:
    now, par, par_col = que.popleft()
    color = 1
    for edge in edges[now]:
        if edge == par:
            continue
        if color == par_col:
            color += 1
        if (now, edge) in edgeind:
            ans[edgeind[(now, edge)]] = color
        else:
            ans[edgeind[(edge, now)]] = color
        que.append((edge, now, color))
        color += 1

print(K)
print('\n'.join([str(a) for a in ans]))

Solution (Python):
from collections import deque
n = int(input())
edge = [[] for _ in range(n)]
ans = [0]*(n-1)
for i in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append((i, v-1))
    edge[v-1].append((i, u-1))


ans[0] = 1
parents = [-1]*n
que = deque([[0, 0]])
while que:
    a, b = que.popleft()
    color = 1
    for i, j in edge[a]:
        if parents[a] == j:
            continue
        if color == b:
            color += 1
        ans[i] = color
        parents[j] = a
        que.append([j, color])
        color += 1
print(max(ans))
for i in ans: print(i)

Solution (Python):
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = 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])

Solution (Python):
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = [0]*(n-1)
    next_node = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        node[i] = (a-1, b-1)
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [0]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = k
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            
    
    for value in node:
        print(ans_list[value])


if __name__ == "__main__":
    main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = mi()
    data[a-1].append((b-1,i))
    data[b-1].append((a-1,i))
    if i == 0:
        num = a-1
        col = 0

ans = [0]*(n-1)
from collections import deque
ima = deque()
ima.append([num,col])
while ima:
    num,col = ima.popleft()
    tmp = 1
    for lis in data[num]:
        if ans[lis[1]] != 0:
            continue
        if tmp == col:
            tmp += 1
        ans[lis[1]] = tmp
        ima.append([lis[0],tmp])
        tmp += 1
a = 0        
for i in range(n-1):
    a = max(a,ans[i])
print(a)
for i in range(n-1):
    print(ans[i])

Solution (Python):

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G


from collections import deque
def bfs(v,p,color):
    q=deque()
    q.append((v,p,0))
    ans={}
    while q:
        
        V,P,NUM=q.popleft()
        num=min(0,NUM)+1
        for new_v in G[V-1]:
            if new_v==P:continue
            if NUM==num:num+=1
            ans[(V,new_v)]=num
            q.append((new_v,V,num))
            num=num+1
    return ans

n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
G=Graph(ab)


color=0
for i in G:
    temp=len(i)
    if color<temp:color=temp
print(color)

ans=bfs(1,-1,color)

for i in ab:
    print(ans[i])

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  G=[[]*n for _ in range(n)]
  vp=[]

  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    vp.append((a,b))

  k=0
  d={}
  cs=[0]*n

  used=[False]*n
  used[0]=True
  q=collections.deque()
  q.append(0)
  while q:
    v=q.popleft()
    k=max(k,len(G[v]))
    cur=1
    for u in G[v]:
      if used[u]:
        continue
      if cur==cs[v]:
        cur+=1
      cs[u]=d[(u,v)]=d[(v,u)]=cur
      cur+=1
      used[u]=True
      q.append(u)

  print(k)
  for a,b in vp:
    print(d[(a,b)])

main()