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

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

r = [0] * (N - 1)
q = deque([(0, 1)])

while q:
  preC, fromv = q.popleft()
  c = 0
  for tov, i in edge[fromv]:
    edge[tov].remove((fromv, i))
    c += 1 + (c + 1 == preC)
    q.append((c, tov))
    r[i] = c
print(max(r))
for x in r:
  print(x)

Solution (Python):
n=int(input())
l=[]
import sys
sys.setrecursionlimit(20000000)
from collections import defaultdict
d=defaultdict(lambda:defaultdict(int))
l1=[[] for i in range(n+1)]

for i in range(n-1):
  a,b=map(int,input().split())
  l1[a].append(b)
  l1[b].append(a)
  l.append([a,b])
max1=0
for i in l1:
  if max1<len(i):
    max1=len(i)
def dfs(x,y):
  l2=l1[x]
  now=1
  for i in range(len(l2)):
    if d[x][l2[i]]!=0:
      pass
    else:                
      if now==y:
        now+=1
      d[x][l2[i]]=now
      d[l2[i]][x]=now
      dfs(l2[i],now)
      now+=1
print(max1)
dfs(1,0)
for i in range(len(l)):
  print(d[l[i][0]][l[i][1]])

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = [set() for _ in range(N)]
ABs = []
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1, b-1
    ABs.append((a,b))
    lines[a].add(b)
    lines[b].add(a)


K = -1
ki = -1
for i in range(N):
    if K < len(lines[i]):
        K = len(lines[i])
        ki = i



colors = [defaultdict(int) for _ in range(N)]

def dfs(s,bs,bk):
    cnt = 0
    for t in lines[s]:
        if t == bs:
            continue
        else:
            if cnt == bk:
                cnt += 1
            colors[s][t] = cnt
            colors[t][s] = cnt
            dfs(t,s,cnt)
            cnt += 1


for i,t in enumerate(lines[ki]):
    colors[ki][t] = i
    colors[t][ki] = i
    dfs(t,ki,i)

print(K)
for a,b in ABs:
    print(colors[a][b]+1)

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

N = int(input())

graph = [[] for i in range(N)]

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

def dfs(past,now,edge_col):
    new_col = 1
    for (future,i) in graph[now-1]:
        if future == past:
            pass
        else:
            if new_col == edge_col:
                new_col += 1
            ans[i] = new_col
            dfs(now,future,new_col)
            new_col += 1
            
dfs(-1,1,-1)

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

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

N = int(input())
edge = [[] for _ in range(N)]
v_dic = {}
b_l = []
for i in range(N-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge[a].append(b)
    if a not in v_dic:
        v_dic[a] = 1
    else:
        v_dic[a] += 1
    if b not in v_dic:
        v_dic[b] = 1
    else:
        v_dic[b] += 1
    b_l.append(b)
colors = [0 for _ in range(N)]


def bfs(p_node, p_color):
    children_node = edge[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1


def solve():
    bfs(0, 0)

    print(max(v_dic.values()))
    for b in b_l:
        print(colors[b])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import queue
input = sys.stdin.readline

N = int(input())
alist = [[] for _ in range(N+1)]
idx = {}
for i in range(N-1):
    a, b = map(int, input().split())
    alist[a].append(b)
    alist[b].append(a)
    idx[(a, b)] = i
    idx[(b, a)] = i

q = queue.Queue()
ans = [0]*(N-1)
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[idx[(n[0], nxt)]] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
print(*ans, sep='\n')

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    ab = []
    for i in range(n-1):
        tma, tmb = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        ab.append([tma-1, tmb-1])

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0]
    ans = collections.defaultdict(int)
    ls = [1] * n
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    fq[tmv]
                    if ls[tmp] == cost:
                        ls[tmp] += 1
                    ql.append([ls[tmp], tmv])
                    ans[tmp, tmv] = ls[tmp]
                    ls[tmp] += 1
        else:
            break
    print(max(ans.values()))
    for a, b in ab:
        print(ans[a, b])


if __name__ == '__main__':
    solve()

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

last_color = 0


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)

Solution (Python):
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0,pu=-1,pc=-1):
        c=1
        for i,cu in to[u]:
            if cu==pu:continue
            if c==pc:c+=1
            ans[i]=c
            dfs(cu,u,c)
            c+=1

    to=defaultdict(list)
    n=int(input())
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append([i,b])
        to[b].append([i, a])
    ans=[-1]*(n-1)
    dfs()
    print(max(ans))
    print(*ans,sep="\n")

main()

Solution (Python):
from collections import deque

N = int(input())

edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append((to, i))
    edges[to].append((fr, i))

que = deque([(1, -1)])
ans = [-1] * (N - 1)
while que:
    now, parent = que.popleft()

    canUse = set(range(1, len(edges[now]) + 1))
    for to, i in edges[now]:
        if to == parent and ans[i] in canUse:
            canUse.remove(ans[i])

    canUse = list(canUse)
    for to, i in edges[now]:
        if to == parent:
            continue
        color = canUse.pop()
        if ans[i] == -1:
            ans[i] = color
        que.append((to, now))

print(max(ans))
print(*ans, sep='\n')

Solution (Python):
import sys


def bfs(p_node, p_color):
    global K
    children_node = graph[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1
    K = max(K, c_color - 1)


sys.setrecursionlimit(10**9)

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

colors = [-1] * (N + 1)
K = 0

bfs(1, -1)

print(K)
for a, b in ab:
    print(colors[b])

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

N = int(input())

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

colors = [-1] * (N + 1)
K = 0


def bfs(p_node, p_color):
    global K
    children_node = graph[p_node]
    c_color = 1
    for child_node in children_node:
        if c_color == p_color:
            c_color += 1
        colors[child_node] = c_color
        bfs(child_node, c_color)
        c_color += 1
    K = max(K, c_color - 1)


bfs(1, -1)

print(K)
for a, b in ab:
    print(colors[b])

Solution (Python):
import sys


		
def main():
	n = int(input())
	
	ttt=[0]*n
	for i in range(n):
		ttt[i]=[]
	
	for i in range(n-1):
		a, b = map(int, input().split())
		ttt[a-1].append([b-1, i])
		ttt[b-1].append([a-1, i])
	
	bb=max([len(t) for t in ttt])	
	print(bb)
	
	ret_ll=[0]*(n-1)
	ss_stack=[(0,-1, bb+100)]
	
	
	while len(ss_stack) > 0:
		st, parent, pp_color = ss_stack.pop()
		
		current_color=1
		if current_color==pp_color:
			current_color+=1
		for i, [path_to, idx] in enumerate(ttt[st]):
			if path_to == parent:
				continue
			
			c_color = current_color
			current_color+=1
			if current_color==pp_color:
				current_color+=1
			
			ret_ll[idx] = c_color
			ss_stack.append([path_to, st, c_color])
			
	for ret in ret_ll:
		print(ret)
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
def coloring2(color,p):
    global K
    dcolor = 1
    for c in Data[p]:
        if dcolor == color:
            dcolor += 1
        s = str(p)+'_'+str(c)
        Edge[s] = dcolor 
        coloring2(dcolor,c)
        dcolor += 1
    K = max(K,dcolor-1)

sys.setrecursionlimit(10 ** 9)
N = int(input())
Data = [ [] for _ in range(N+1) ]
Edge = {} 
Edge2 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    Data[a].append(b)
    s = str(a)+'_'+str(b)
    Edge[s] = 0
    Edge2.append([a,b])

K = 0
coloring2(0,1)
print(K)
for [a,b] in Edge2:
    s = str(a)+'_'+str(b)
    print(Edge[s])

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

n = int(input())
edges = [tuple([int(i) for i in input().split()]) for _ in range(n - 1)]
graph = [0] + [[] for _ in range(n)]

for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

max_color_index = 1
def bfs(graph, dist, queue, parent_colors, color_map):
    global max_color_index
    while queue:
        parent = queue.pop(0)
        children = graph[parent]

        color_index = 1
        for child in children:
            if dist[child] != -1:
                continue

            
            
            if parent_colors[parent] == color_index:
                color_index += 1

            e = (min(child, parent), max(child, parent))
            if e not in color_map:
                color_map[e] = color_index

            parent_colors[child] = color_index
            color_index += 1

            dist[child] = dist[parent] + 1
            queue.append(child)

        
        max_color_index = max(max_color_index, color_index - 1)

dist = [0] + [-1] * n
dist[1] = 0
queue = [1]
parent_color = [0] * (n + 1)
color_map = {}
bfs(graph, dist, queue, parent_color, color_map)

print(max_color_index)
for e in edges:
    print(color_map[e])

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

n = int(input())
edges = [tuple([int(i) for i in input().split()]) for _ in range(n - 1)]
graph = [0] + [[] for _ in range(n)]

for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

max_color_index = 1
def bfs(graph, dist, queue, parent_colors, color_map):
    global max_color_index
    while queue:
        parent = queue.pop(0)
        children = graph[parent]

        color_index = 1
        for child in children:
            if dist[child] != -1:
                continue

            
            
            if parent_colors[parent] == color_index:
                color_index += 1

            e = (min(child, parent), max(child, parent))
            if e not in color_map:
                color_map[e] = color_index

            parent_colors[child] = color_index
            color_index += 1

            dist[child] = dist[parent] + 1
            queue.append(child)

        
        max_color_index = max(max_color_index, color_index - 1)

dist = [0] + [-1] * n
dist[1] = 0
queue = [1]
parent_color = [0] * (n + 1)
color_map = {}
bfs(graph, dist, queue, parent_color, color_map)

print(max_color_index)
for e in edges:
    print(color_map[e])

Solution (Python):
import sys


sys.setrecursionlimit(10 ** 6)

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


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)

Solution (Python):

import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    h = [[] for _ in range(N+1)]    

    for i in range(N-1):
        h[a[i]].append(b[i])
        h[b[i]].append(a[i])

    queue = deque([1])

    
    parents = [0]*(N+1)
    order = []

    while queue:
        q = queue.pop()
        order.append(q)

        for child in h[q]:
            if child == parents[q]:
                continue

            parents[child] = q
            queue.append(child)

    
    color = [0]*(N+1)

    for o in order:
        ng_color = color[o]
        cur_color = 1

        for node in h[o]:
            if node == parents[o]:
                continue

            if cur_color == ng_color:
                cur_color += 1
            
            color[node] = cur_color
            cur_color += 1


    answer = []
    append = answer.append
    for i in range(N-1):
        if parents[a[i]] == b[i]:
            append(color[a[i]])
        else:
            append(color[b[i]])

    print(max(answer))
    print(*answer, sep="\n")

    return


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

if __name__ == '__main__':
    main()

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

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

def dfs(v, c=-1, p=-1):
    k = 1
    for nv, ei in edges[v]:
        if nv == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(nv, ans[ei], v)

ans = [None]*(n-1)
dfs(0)

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

Solution (Python):

import sys

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

    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    root = 1
    parent = [None] * (n + 1)
    
    checked = []
    to_check = [root]
    
    
    

    while to_check:
        x = to_check.pop()
        
        for y in graph[x]: 
            if y == parent[x]: 
                continue
            
            parent[y] = x 
            to_check.append(y) 
        checked.append(x) 

    color = [None] * (n + 1) 
    
    
    for x in checked: 
        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

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

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys

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

    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    root = 1
    parent = [None] * (n + 1)
    
    checked = []
    to_check = [root]
    
    
    

    while to_check:
        x = to_check.pop()
        
        for y in graph[x]: 
            if y == parent[x]: 
                continue
            
            parent[y] = x 
            to_check.append(y) 
        checked.append(x) 

    color = [-1] * (n + 1) 
    for x in checked: 
        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

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

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys

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

    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    root = 1
    parent = [0] * (n + 1)
    order = []
    stack = [root]

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

    color = [-1] * (n + 1)
    for x in order:
        ng = color[x]
        c = 1
        for y in graph[x]:
            if y == parent[x]:
                continue
            if c == ng:
                c += 1
            color[y] = c
            c += 1

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

    print(max(res))
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

q, ans = deque(), [0] * (N - 1)
q.append((0, 0))

while len(q) > 0:
    (c, n), ac = q.popleft(), 1
    for l, i in P[n]:
        if ac == c:
            ac += 1
        q.append((ac, l))
        ans[i] = ac
        ac += 1

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

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

N, *ab = map(int, read().split())

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

Solution (Python):
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])

while stack:
    a=stack.popleft()
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        P[b].remove(a)
    P[a].clear()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=[[] for i in range(n)]
d=[]
for i in range(n-1):
  c[l[i][0]-1].append(l[i][1]-1)
  c[l[i][1]-1].append(l[i][0]-1)
for i in range(n):
  d.append(len(c[i]))
print(max(d))
dmax=d.index(max(d))

def bfs(v):
  child=[[] for i in range(n)]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  colorL=[set() for i in range(n)]
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        color=0
        for j in range(len(c[next[i]])):
          if visited[c[next[i]][j]]==-1:
            color+=1
            while color in colorL[next[i]]:
              color+=1
            child[next[i]].append((c[next[i]][j],color))
            next2.add(c[next[i]][j])
            colorL[c[next[i]][j]].add(color)
    next=list(next2)
    next2=set()
  return child

bfs=bfs(dmax)
ans={}
for i in range(n):
  for j in range(len(bfs[i])):
    ans[min(bfs[i][j][0],i)+1,max(bfs[i][j][0],i)+1]=bfs[i][j][1]

for i in range(n-1):
  print(ans[l[i][0],l[i][1]])

Solution (Python):
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]
for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    a=stack.popleft()
    count=1
    for b in P[a]:
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        P[b].remove(a)
    P[a].clear()


print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


def f(a, b):
    return (a, b) if a < b else (b, a)


def dfs(s, p):
    used = {}
    for t in g[s]:
        idx = rev[f(s, t)]
        if ans[idx] > 0:
            used[ans[idx]] = True 
    c = 1
    for t in g[s]:
        idx = rev[f(s, t)]
        if t == p or ans[idx] > 0:
            continue
        while c in used:
            c += 1
        ans[idx] = c
        c += 1
        dfs(t, s)
        

n = int(input())
g = [[] for _ in range(n)]
rev = {}
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    g[a].append(b)
    g[b].append(a)
    rev[(a, b)] = i
ans = [0] * (n - 1)
dfs(0, -1)
print(max(ans), *ans, sep='\n')

Solution (Python):
import sys
N = int(input().strip())

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

for i in range(N-1):
    a, b = 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





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

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    
    tmp_color = 1
    for edge in n_list[node]:
        
        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]) 
for i in range(N-1):
    print(colors[i])

Solution (Python):
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    
    
    a=stack[0]
    count=1
    for b in P[a]:
        
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

Solution (Python):
import math
import os
import sys
from collections import deque

input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)
    init = -1
    display_order = []

    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
        display_order.append(v-1)

    q = deque()
    q.append((1, 0))
    visited = [False] * (N + 1)
    visited[1] = True

    while len(q) != 0:
        idx, color = q.popleft()
        nxt = graph[idx]
        cnt = 1
        
        for e in nxt:
            if colors[e] == -1 and not visited[e]:
                if cnt == color:
                    cnt += 1
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1
                else:
                    colors[e] = cnt
                    q.append((e, cnt))
                    visited[e] = True
                    cnt += 1

    print(max(colors))
    
    
    for i in display_order:
        
        print(colors[i+1])
    
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    
    
    a=stack[0]
    count=1
    for b in P[a]:
        
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])

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

N = int(input())


A = []
for i in range(N - 1):
    A.append([int(i)-1 for i in input().split()])

B = []
for row in A:
    B.append(sorted(row))
B.sort(key = itemgetter(0))

link_list = [[] for i in range(N)]
for row in B:
    link_list[row[0]].append(row[1])
    link_list[row[1]].append(row[0])
edge_color = dict()
marker = [0] * N


def DFS_color(node, pre_color):
    target_list = link_list[node]
    color = 1
    for ko_node in target_list:
        if marker[ko_node] == 0:
            if pre_color == color:
                color += 1
            edge_color[node, ko_node] = color
            edge_color[ko_node, node] = color 
            marker[ko_node] = 1
            DFS_color(ko_node, color)
            color += 1
        else:
            pass

marker[0] = 1
DFS_color(0, 0)

print(max(edge_color.values()))
for node1, node2 in A:
    print(edge_color[node1, node2])

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

n=int(input())

tree=[set() for i in range(n)]
edges=[tuple(map(int,input().split())) for i in range(n-1)]
edge_color={}
for a,b in edges:
    a-=1
    b-=1
    tree[a].add(b)
    tree[b].add(a)
k = 0
for i in range(n):
    k = max(k,len(tree[i]))

for a,b in edges:
    edge_color[(a-1,b-1)] = 0

def colorize(u,v,c,init=False):
    if not init:
        edge_color[(min(u,v),max(u,v))] = c
    cc = c+1
    if cc > k:
        cc = 1
    for x in tree[u]:
        if edge_color[(min(x,u),max(x,u))] == 0:
            colorize(x,u,cc)
            cc += 1
            if cc > k:
                cc = 1

colorize(0,1,1,True)
print(k)
for a,b in edges:
    print(edge_color[(a-1,b-1)])

Solution (Python):
import sys
read = sys.stdin.read


n, *ab = map(int, read().split())
ans = [0]*(n-1)
edges = [[]for _ in range(n)]
used = [0]*n

for i, a, b in zip(range(n-1), *[iter(ab)] * 2):
    edges[a-1].append([b-1, i])

for node in range(n):
    unable = used[node]
    color = 1

    for to, id in edges[node]:
        if color == unable:
            color += 1
        ans[id] = str(color)
        used[to] = color
        color += 1

print(max(used))
print('\n'.join(ans))

Solution (Python):
n=int(input())
edges=[]
relations={}
nodes=[0,0]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    relations.setdefault(a,[]).append(b)
    nodes.append(0)

max_color=0
for start in range(1,n+1):
    targets=relations.get(start,[])
    color=1
    for target in targets:
        if color == nodes[start]:
            color+=1
        else:
            pass
        nodes[target]=color
        if color>=max_color:
            max_color=color
        color+=1

print(max_color)
for edge in edges:
    print(nodes[edge[1]])

Solution (Python):
from collections import Counter, defaultdict
from sys import getrecursionlimit,setrecursionlimit
setrecursionlimit(100*getrecursionlimit())
G = defaultdict(list)
C = Counter()
N = int(input())
ans = {}
o = []
for i in range(N-1):
    a, b = 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)])