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
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1]) 
    parent = [None] * (n + 1)
    color = [None] * (n + 1) 

    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 1
            
    print(max(color[2:]))

    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1]) 
    parent = [None] * (n + 1)
    color = [0] * (n + 1) 

    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 1
            
    print(max(color))

    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import numpy as np

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2)

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    parent = np.zeros(n + 1, dtype=np.int64)
    color = np.zeros(n + 1, dtype=np.int64) 

    q = deque([1]) 
    while q:
        x = q.popleft()
        ng = color[x]
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if c == ng:
                c += 1
            color[y] = c
            q.append(y)
            c += 1

    print(np.amax(color))

    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def main():
    n = int(sys.stdin.readline().rstrip())
    ab = map(int, sys.stdin.read().split())
    ab = list(zip(ab, ab))

    G = [[] for _ in range(n + 1)]
    for a, b in ab:
        G[a].append(b)
        G[b].append(a)
    
    root = 1
    q = deque()
    q.append(root)
    parent = [None] * (n + 1)
    color = [0] * (n + 1) 

    while q:
        x = q.popleft()
        c = 1
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            if color[x] == c:
                c += 1
            color[y] = c
            c += 1
            q.append(y)

    res = []
    for a, b in ab:
        if a == parent[b]:
            res.append(color[b])
        else:
            res.append(color[a])
    
    k = max(color)
    print(k)
    print('\n'.join(map(str, res)))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(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])
  
  for y, i in e[x]:
    
    while t in viss:
      t += 1
    if i in vis:
      continue
    
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
    dfs(y)
  
dfs(1)
print(max(res))
for r in res: print(r)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(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])
  
  for y, i in e[x]:
    
    while t in viss:
      t += 1
    if i in vis:
      continue
    
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
  for y in svis:
    dfs(y)
  
dfs(1)
print(max(res))
for r in res: print(r)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
ki =[[] for _ in range(N)]
ab = []
dict = {}
k = 0
def dfs(v, p = 0, ban_color = 0):
    global k
    color = 1
    for i in ki[v]:
        if i == p:
            continue
        if ban_color == color:
            color += 1
        dict[(v, i)] = color
        dfs(i, v, color)
        color += 1
    k = max(k, color - 1)
    return


for i in range(N - 1):
    a, b = map(int, input().split())
    ki[a - 1].append(b - 1)
    ki[b - 1].append(a - 1)
    ab.append((a - 1, b - 1))

dfs(0)
print(k)
for key in ab:
    print(dict[key])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(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])

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines













from collections import deque













def main():
	n=int(input())
	E=[[] for i in range(n+1)]
	O=[]
	for i in range(n-1):
		a,b=map(int,input().split())
		E[a].append(b)
		O.append(b)
		
	C=[0]*(n+1)
	q = deque([1])
	while q:
		now = q.popleft()
		cnt=1
		for i in E[now]:
			if cnt==C[now]:
				cnt+=1
			C[i]=cnt
			cnt+=1
			q.append(i)
	print(max(C))
	for i in O:
		print(C[i])
	
	
if __name__ == "__main__":
		main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


for i in range(N-1):
  a,b=map(int,input().split())
  v[a-1].append([b-1,0,i])
  v[b-1].append([a-1,0,i])

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])

Solution (Python):
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

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

main()

Solution (Python):
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

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].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), *(C[b] for b in B))

main()

Solution (Python):
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

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

main()

Solution (Python):
"""
challenge case

in:
3
1 3
2 3

out:
1
1
1
"""

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

Solution (Python):
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())
    A, B = AB[::2], AB[1::2]

    E = [[] for _ in range(N + 1)]
    for a, b in zip(A, B):
        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])

main()

Solution (Python):
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    B = AB[1::2]
    for a, b in zip(*[iter(AB)] * 2):
        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])

main()

Solution (Python):
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    I = []
    for a, b in zip(*[iter(AB)] * 2):
        E[a].append(b)
        I.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 i in I:
        print(C[i])

main()

Solution (Python):
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]

memo = {}
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].append(b)
    E[b].append(a)
    memo[(a, b)] = i
    memo[(b, a)] = i

K = max(len(e) for e in E)

A = [0] * (N - 1)

cand = {i for i in range(1, K + 1)}

visited = [False] * (N + 1)

Q = deque([(-1, 1)])
visited[1] = True
while Q:
    p, v = Q.popleft()
    c = 0
    for u in E[v]:
        if visited[u]:
            continue
        visited[u] = True
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

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

Solution (Python):
import queue
n = int(input())



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


li = []

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


ans = [0] * (n-1)

q = queue.Queue()
check = [0] * (n+1)

check_color = [0] * (n+1)

q.put(1)
color_num = 1


while not q.empty():
    tmp_color = 0
    tmp = q.get()
    
    
    mae_color = check_color[tmp]
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i][0]] == 1:
            
            continue
        else:
            
            tmp_color += 1
            q.put(ab[tmp][i][0])
            if tmp_color == mae_color:
                tmp_color += 1
            check_color[ab[tmp][i][0]] = tmp_color
            ans[ab[tmp][i][1]] = tmp_color
            
            
            check[tmp] = 1
            if color_num < tmp_color:
                color_num = tmp_color
            
            

print(color_num)
for i in range(len(ans)):
    print(ans[i])

Solution (Python):
import queue
n = int(input())



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


li = []

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


ans = [0] * (n-1)

q = queue.Queue()
check = [0] * (n+1)

check_color = [0] * (n+1)

q.put(1)
color_num = 1


while not q.empty():
    tmp_color = 0
    tmp = q.get()
    
    
    mae_color = check_color[tmp]
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i][0]] == 1:
            
            continue
        else:
            
            tmp_color += 1
            q.put(ab[tmp][i][0])
            if tmp_color == mae_color:
                tmp_color += 1
            check_color[ab[tmp][i][0]] = tmp_color
            ans[ab[tmp][i][1]] = tmp_color
            
            
            check[tmp] = 1
            if color_num < tmp_color:
                color_num = tmp_color
            
            

print(color_num)
for i in range(len(ans)):
    print(ans[i])

Solution (Python):
class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(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)

Solution (Python):
import sys
from collections import deque
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 = 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.append((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Solution (Python):
import sys
from collections import deque
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 = 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)

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

Solution (Python):


from collections import deque

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

tree = {}
node_in = [0 for i in range(n)] 
node_out = [[0] for i in range(n)] 
for edge in sorted(edges):
    a = edge[0] 
    b = edge[1] 

    color = 0
    if node_out[a-1][-1] == 0:
        if node_in[a-1] <= 1: 
            color = node_in[a-1] + 1
        else: 
            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] 
    b = edge[1] 
    print(tree[(a, b)])

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

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

Solution (Python):
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)
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.append((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

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

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

Solution (Python):
from collections import deque

N = int(input())
vertex_neighbor_vertices = {}  
vertex_colors = {}  
sides = []  
side_color = {}  


def add_neighbors(start, end):
    neighbors_of_s = set()
    if start in vertex_neighbor_vertices:
        neighbors_of_s = vertex_neighbor_vertices[start]
    else:
        vertex_neighbor_vertices[start] = neighbors_of_s
    neighbors_of_s.add(end)


def init_colors(vertex):
    colors = set()
    if vertex not in vertex_colors:
        vertex_colors[vertex] = colors


def get_unused_color(colors_of_sv, colors_of_ev, color_start):
    for i in range(color_start, N + 1):
        if (i not in colors_of_sv) and (i not in colors_of_ev):
            return i


for i in range(N - 1):
    s, e = map(int, input().split())
    sides.append((s, e))
    add_neighbors(s, e)
    add_neighbors(e, s)
    init_colors(s)
    init_colors(e)

max_color_num = 0
max_neighbor_vertex = 0
for k, v in vertex_neighbor_vertices.items():
    if len(v) > max_color_num:
        max_color_num = len(v)
        max_neighbor_vertex = k

print(max_color_num)


visited = set()
q = deque([max_neighbor_vertex])

while q:
    vertex = q.popleft()
    visited.add(vertex)
    
    color_start = 1
    for neighbor in vertex_neighbor_vertices[vertex]:
        if neighbor in visited:
            continue
        q.append(neighbor)
        color = get_unused_color(vertex_colors[vertex], vertex_colors[neighbor], color_start)
        color_start = color + 1
        vertex_colors[vertex].add(color)
        vertex_colors[neighbor].add(color)
        side_color[(vertex, neighbor)] = color

for s, e in sides:
    color = 0
    if (s, e) in side_color:
        color = side_color[(s, e)]
    else:
        color = side_color[(e, s)]
    print(color)

Solution (Python):
from collections import defaultdict

N = int(input())
num_of_edge = [0] * N
edge = defaultdict(list)

for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append((b, i))
    edge[b].append((a, i))
    num_of_edge[a] += 1
    num_of_edge[b] += 1

K = max(num_of_edge)

ans = [0] * (N-1)
stack = [(0, -1, 0)]
while stack:
    cur, past, color = stack.pop()
    color_cand = 1
    for cand, num in edge[cur]:
        if cand != past:
            if color_cand == color:
                color_cand += 1
            ans[num] = color_cand
            stack.append((cand, cur, color_cand))
            color_cand += 1

print(K)
for i in range(len(ans)):
    print(ans[i])

Solution (Python):
import queue as qu
import bisect



def resolve():
    N=int(input())
    nod=[[[],[]] for i in range(N)]
    path=[[] for i in range(N-1)]
    col=[0 for i in range(N-1)]


    for i in range(N-1):
        path[i]=[int(i)-1 for i in input().split()]
        nod[path[i][1]][0].append(i)
        nod[path[i][0]][0].append(i)
    mx=0
    mnod=0
    for i in range(N):
        if len(nod[i][0])>mx:
            mx=len(nod[i][0])
            mnod=i
    print(mx)

    q=qu.Queue(N)
    q.put(mnod)

    while not q.empty():

        tagnod=q.get()
        nod[tagnod][1].sort()
        nod[tagnod][0].sort()
        cc=1
        pointer=0
        for i in range(len(nod[tagnod][0])-1,-1,-1):
            tp=nod[tagnod][0][i]

            while pointer<len(nod[tagnod][1]) and nod[tagnod][1][pointer] == cc:
                cc+=1
                pointer+=1
            col[tp]=cc
            if tagnod==path[tp][0]:
                nnod=path[tp][1]
            else:
                nnod=path[tp][0]

            bisect.insort(nod[nnod][1],cc)
            nod[nnod][0].remove(tp)
            q.put(nnod)
            cc+=1

    for i in col:
        print(i)





if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque


def main():
    N = int(input())
    C = []
    T = [[] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = [int(x) for x in input().split()]
        T[a].append([b, i])
        T[b].append([a, i])
        C.append(a)
        C.append(b)
    

    q = deque()
    q.append([1, 0])

    visited = set()
    ans = [0] * N
    while q:
        i, color = q.popleft()
        visited.add(i)
        now_color = 0
        for v, j in T[i]:
            if not v in visited:
                now_color += 1
                if now_color == color:
                    now_color += 1
                q.append([v, now_color])
                ans[j] = now_color
    
    print(max(ans))
    for i in range(N - 1):
        print(ans[i])



    

    



if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from collections import deque


def main():
    N = int(input())
    C = []
    T = [[] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = [int(x) for x in input().split()]
        T[a].append([b, i])
        T[b].append([a, i])
        C.append(a)
        C.append(b)
    
    c = Counter(C)
    print(c.most_common(1)[0][1])

    q = deque()
    q.append([1, 0])


    visited = set()
    ans = [0] * N

    while q:
        i, color = q.popleft()
        visited.add(i)
        now_color = 0
        for v, j in T[i]:
            if not v in visited:
                now_color += 1
                if now_color == color:
                    now_color += 1
                q.append([v, now_color])
                ans[j] = now_color
    
    for i in range(N - 1):
        print(ans[i])



    

    



if __name__ == '__main__':
    main()

Solution (Python):
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, c = -1 , p = -1):
    k = 1    
    for e in node.edge:
        if e == p:
            continue
        if k == c:
            k += 1
        
        child = tree[e]

        
        if a < b:
            ans['{0} {1}'.format(node.num, child.num)] = k
        else:
            ans['{0} {1}'.format(child.num, node.num)] = k
        k += 1

        
        dfs(child,k - 1, node.num)


N = int(input())
ans = {}



tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)




count = 0
for node in tree:
    count = max(count, len(node.edge))
print(count)
for edge in edges:
    
    print(str(ans.get(edge)))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
aa = [0] * (n-1)
bb = [0] * (n-1)
g = [[] for i in range(n)]
res = defaultdict(lambda : defaultdict(int))
for i in range(n-1):
    a,b = inpl()
    aa[i] = a-1
    bb[i] = b-1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def dfs(i,c=-1,p=-1):
    
    cnt = 1
    for j in g[i]:
        
        if j == p:
            continue
        if cnt == c:
            cnt += 1
        res[i][j] = cnt
        res[j][i] = cnt
        cnt += 1
        dfs(j,res[i][j],i)
dfs(0)
m = 0
for i in g:
    m = max(m, len(i))
print(m)
for i in range(n-1):
    print(res[aa[i]][bb[i]])

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

Solution (Python):
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 = [None]*(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])

Solution (Python):
import sys
input = sys.stdin.readline
 
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]


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:
    
    n = stack.pop()
    order.append(n)
    for j in graph[n]:
        
        if j == parent[n]:
            continue
        parent[j] = n
        stack.append(j)


color = [-1] * (N+1)

for i in order:
    
    ng = color[i]
    
    c = 1
    for j in graph[i]:
        
        if j == parent[i]:
            continue
        if c == ng:
            c += 1
        
        color[j] = c
        c += 1


answer = [color[a] if parent[a]==b else color[b] for a,b in AB]
print(max(answer))
print("\n".join(map(str,answer)))