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

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=0
for e in E:
    k=max(k,len(e))
ans=[0]*(n-1)
def dsf(v,p,vp_c):
    c=1
    for u,i in E[v]:
        if u!=p:
            if c==vp_c:
                c+=1
            ans[i]=c
            dsf(u,v,c)
            c+=1
dsf(1,0,0)
print(k)
for i in range(n-1):
    print(ans[i])

Solution (Python):
n=int(input())
s=[[]for _ in range(n)]
d={}
f=[]
for i in range(n-1):
  a,b=map(int,input().split())
  d[min(a,b)*1000000+max(a,b)]=10**7
  s[a-1].append(b-1)
  s[b-1].append(a-1)
  f.append((a-1,b-1))
se={0}
mc=max(len(s[i])for i in range(n))
print(mc)
Q=[(0,i)for i in s[0]]
r=[-1]*n
r[0]=0
while Q:
  P=[]
  b=-1
  for i,j in Q:
    if j in se:continue
    if b!=i:x=1
    else:x+=1
    if r[i]==x:x+=1
    b=i
    se.add(j)
    for k in s[j]:
      P.append((j,k))
    d[min(i,j)*1000000+max(i,j)]=x
    r[j]=x
  Q=P
for i,j in f:print(d[min(i,j)*1000000+max(i,j)])

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

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

def main():
    N = int(readline())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    m = map(int,read().split())
    AB = list(zip(m,m))
    for a, b in AB:
        E[a].append(b)
        edge_order.append(b)
    
    
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

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

def main():
    N, *ab = map(int, read().split())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    for a, b in zip(*[iter(ab)] * 2):
        E[a].append(b)
        edge_order.append(b)
    
    
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

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

def main():
    N, *ab = map(int, read().split())
    E = [[] for _ in range(N + 1)]
    edge_order = []
    
    for a, b in zip(*[iter(ab)] * 2):
        E[a].append(b)
        edge_order.append(b)
    
    
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

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

N = int(input())
adj = [[] for i in range(N)]
ran = [0]*N
ans = [0]*(N-1)
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    adj[a].append([b,i])
    adj[b].append([a,i])
    ran[a]+=1
    ran[b]+=1
K = max(ran)
ind = ran.index(K)
print(K)

que = [[ind,0]]
while len(que)!=0:
    i,c = que.pop(0)
    col = 1
    for jlis in adj[i]:
        if col == c:
            col += 1
        if ans[jlis[1]]==0:
            ans[jlis[1]] = col
            que.append([jlis[0],col])
            col += 1
print("\n".join([str(i) for i in ans]))

Solution (Python):

import sys
sys.setrecursionlimit(100000)

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

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

    def dfs(focus,parent_color):
        if focus == N-1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 
            ans[index] = color
            
            
            dfs(child,color)
            color += 1 

    dfs(0,0)

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
l = [[] for _ in range(n)]
ans = [0]*(n-1)
q = deque()
color = [0]*n 
count = 0
for i in range(n-1):
    x,y = map(lambda x: int(x)-1, input().split())
    if i == 0:
        q.append(x) 
    l[x].append((y,i))
    l[y].append((x,i))
while count<n-1:
    node = q.popleft()
    c = 1
    for d, ind in l[node]:
        if ans[ind] == 0:
            if c == color[node]:
                c += 1
            ans[ind] = c
            q.append(d) 
            color[d] = c 
            c += 1
            count += 1
print(max(ans))
for i in ans:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(500000)


n = int(input())
lis = [[]for _ in range(n+1)]

for i in range(n-1):
    a,b = map(int,input().split())
    lis[a].append((b,i))
    lis[b].append((a,i))
k = max(len(li) for li in lis)
print(k)
ans = [-1] * (n-1)
def dfs(v = 1, p = 0, p_col = -1):
    col = 1
    for u,idx in lis[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())
G = [[] for i in range(n)]
root = 0
color_num = 0

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))
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])




print(color_num)  
queue = [(root, -1)]
checked = set()
answer = [-1] * (n - 1)

while len(queue) > 0:
  node, c = queue.pop(0)
  color = 1
  for node2, index in G[node]:
    if node2 not in checked:
      if color == c:
        color = c + 1
      answer[index] = color
      color += 1
      queue.append((node2, answer[index]))
  checked.add(node)
print('\n'.join(map(str, answer)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
child_list = [[] for i in range(n)]

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

ans = [None]*(n-1)


def rec(node, parent_color_id):
    default_color_id = 1
    color_id = default_color_id

    for child_node, no in child_list[node]:
        if parent_color_id == color_id:
            color_id += 1
        ans[no] = color_id
        rec(child_node, color_id)
        color_id += 1


rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

Solution (Python):
from collections import deque

N = int(input())
E = [[] for i in range(N+1)]
edge_order = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    edge_order.append(b)
queue = deque([1])
color = [0] * (N+1)
while queue:
    V = queue.popleft()
    c = 1
    for i in E[V]:
        if c == color[V]:
            c += 1
        color[i] = c
        c += 1
        queue.append(i)
print(max(color))
for i in edge_order:
    print(color[i])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,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

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

Solution (Python):
from collections import deque

n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	a, b = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
 
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
 
print(max(ans))
for node in node_list:
	print(ans[node])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main():
    N = int(input())
    bl = []
    d = {i:0 for i in range(1,N+1)}
    d1 = {i:[] for i in range(1,N+1)}
    d2 = {}
    d3 = [0] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        d2[tuple(sorted([a,b]))] = i
        d[a] += 1
        d[b] += 1
        d1[a].append(b)
        d1[b].append(a)
    m = 0
    for i in d:
        m = max(m, d[i])
    dfs(1, d1, d2, d3, 0)
    print(m)
    for i in d3:
        print(i)

def dfs(n, d1, d2, d3, c):
    count = 1
    for i in d1[n]:
        if d3[d2[tuple(sorted([n,i]))]] > 0:
            continue
        if count == c:
            count += 1
        d3[d2[tuple(sorted([n,i]))]] = count
        dfs(i, d1, d2, d3, count)
        count += 1
main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main():
    N = int(input())
    bl = []
    d = {i:0 for i in range(1,N+1)}
    d1 = {i:[] for i in range(1,N+1)}
    d2 = {}
    d3 = [0] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        d2[tuple(sorted([a,b]))] = i
        d[a] += 1
        d[b] += 1
        d1[a].append(b)
        d1[b].append(a)
    m = 0
    for i in d:
        m = max(m, d[i])
    dfs(1, d1, d2, d3, 0)
    print(m)
    for i in d3:
        print(i)

def dfs(n, d1, d2, d3, c):
    count = 1
    for i in d1[n]:
        if d3[d2[tuple(sorted([n,i]))]] > 0:
            continue
        if count == c:
            count += 1
        d3[d2[tuple(sorted([n,i]))]] = count
        dfs(i, d1, d2, d3, count)
        count += 1
main()

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

que = deque()
que.append([0, 0])

watch = [False] * n
watch[0] = True
color = [0] * (n-1)

while que:
    i, prev_color = que.popleft()
    watch[i] = True
    max_color = 1
    for next, index in g[i]:
        if watch[next]: continue
        watch[next] = True
        if max_color == prev_color:
            max_color += 1
        que.append([next, max_color])
        color[index] = max_color
        max_color += 1

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

Solution (Python):
from collections import deque


N = int(input())

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



queue = deque([1])
color = [0] * (N+1)
while queue:
    V = queue.popleft()
    c = 1
    for i in E[V]:
        if c == color[V]:
            c += 1
        color[i] = c
        c += 1
        queue.append(i)

print(max(color))
for i in edge_order:
    print(color[i])

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

N = int(input())
g = [[] for _ in range(N)]
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))

ans = [0] * (N-1)

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

dfs(0)
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):
from collections import deque
def main():
    N = int(input())
    
    E = [[] for i in range(N+1)]
    edge_order = []
    for i in range(N-1):
        a,b = map(int, input().split())
        E[a].append(b)
        edge_order.append(b)
    
    
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def main():
    N = int(input())
    
    E = [[] for i in range(N+1)]
    edge_order = []
    for i in range(N-1):
        a,b = map(int, input().split())
        E[a].append(b)
        edge_order.append(b)
    
    
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if i < V:
                continue
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

Solution (Python):
import math
import sys

UNDEF=-1
sys.setrecursionlimit(1000010)
N = int(input())

V=[[UNDEF,UNDEF,[],[] ] for _ in range(N) ]      
E=[[] for _ in range(N-1) ]    

for i in range(N-1):
    (xa,xb) = map(int,input().split())
    
    E[i]=[xa,xb]
    V[xb-1][0]=xa
    V[xb-1][1]=i+1
    V[xa-1][2].append(xb)
    V[xa-1][3].append(i+1)





def root_v():
    global UNDEF
    global V
    for i in range(len(V)):
        if V[i][0] == UNDEF:
            return i+1
    return UNDEF



def max_degree(s):
    if V[s-1][0] != UNDEF: 
        degree=len(V[s-1][2]) + 1 
    else:
        degree=len(V[s-1][2])     

    for c in V[s-1][2]:
        degree = max ( degree, max_degree(c) ) 
    return degree


print(max_degree(root_v()))


color=[UNDEF for _ in range(N-1)]

def put_colors(s):
    
    global color 
    pcolor=UNDEF
    if V[s-1][1] != UNDEF:
        pcolor = color[V[s-1][1]-1]
    ic = 1
    for i in range(len(V[s-1][3])):
        if ic == pcolor:
            ic = ic + 1
        
        color[V[s-1][3][i]-1] = ic 
        put_colors(V[s-1][2][i])
        ic = ic + 1
    
put_colors(root_v())
for i in range(N-1):
    print(color[i])

Solution (Python):

import sys
sys.setrecursionlimit(100000)

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

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

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 

    dfs(0,0)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])

Solution (Python):


import sys
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
sys.setrecursionlimit(n * 10)
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

Solution (Python):
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  

ans = {}  

q = deque([0])  
colors = [-1]*N  
visited[0] = True
while len(q):  
    v = q.pop()  
    color = 1
    for e in tree[v]:  
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []
ans = []

class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id

def dfs(v, fr, frk):
    global ans
    k = 1
    for e in G[v]:
        if e.to != fr:
            if k == frk:
                k += 1
            ans[e.id] = k
            dfs(e.to, v, k)
            k += 1

def main():
    global G, ans
    n = int(input().strip())
    ans = [0] * (n-1)
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int, input().strip().split()))
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    dfs(0, -1, -1)
    maxk = 0
    for l in G:
        maxk = max(maxk, len(l))
    print(maxk)
    for p in ans:
        print(p)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
l.sort()
flg = [0 for _ in range(n+1)]
ans = [0 for _ in range(n)]

t=0
count=0
for i in range(n-1):
    a,b,c=l[i]
    if t!=a:
        t=a
        count=1
    if flg[a]==count:
        count+=1
    flg[b]=count
    ans[c]=count
    count+=1
    
print(max(flg))
for i in range(1,n):
    print(ans[i])

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

N = int(input())

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

result = [0]*(N-1)
def search(par, ans, own, par_num):
    ans =  max(ans, len(ki[own]))
    i = 1
    for child in ki[own]:
        if child[0] == par:
            continue
        else:
            if i == par_num:
                i += 1
            result[child[1]] = i
            ans = max(search(own, ans, child[0], i),ans)
            i += 1
    return ans

print(search(-1, 0, 0, -1))
for i in result:
    print(i)

Solution (Python):


import sys
sys.setrecursionlimit(100000)

def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())

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

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

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

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




if __name__ == '__main__':
    main()

Solution (Python):
from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

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

n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n-1)

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

def dfs(v, p, pc):
    c = 1
    for nv, edge in t[v]:
        if nv == p: continue
        if c == pc: c += 1
        color[edge] = c
        dfs(nv, v, c)
        c += 1

dfs(0, -1, 0)
print(max(color))
print(*color, sep="\n")

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(ver, color):
    
    cnt = 1
    
    for (to, i) in G[ver]:
        
        if cnt==color:
            cnt += 1
        
        ans[i] = cnt
        
        func(to, cnt)
        
        cnt += 1

func(0, 0)

print(max(ans))

print(*ans, sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
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())
    a,b = a-1,b-1
    G[a].append([b,i])

ans = [None]*(n-1)
def rec(cur,color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1
rec(0, 0)
print(max(ans))
print(*ans, sep="\n")

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

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

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(100000)


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

Solution (Python):

from collections import deque












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

K = [0]*N
for ab in AB:
    a,b,i = ab
    K[a-1]+=1
    K[b-1]+=1
k = max(K)
print(k)
AB.sort()
C = [0]*N
D = deque(AB)
flag = 0
visited = [-1]*N
ans = [0]*(N-1)
while D:
    a,b,i = D.popleft()
    if visited[a-1] == -1 and visited[b-1] == -1:
        if flag == 0:
            flag = 1
            visited[a-1] = 0
            visited[b-1] = 0
            ans[i] = 1
            C[a-1] = 1
            C[b-1] = 1
        else:
            D.append([a,b,i])
    else:
        if visited[b-1] == -1:
            if C[a-1] == k:
                ans[i] = 1
                C[a-1] = 1
                C[b-1] = 1
            else:
                ans[i] = C[a-1]+1
                C[a-1]+=1
                C[b-1] = C[a-1]
            visited[b-1] = 0
        else:
            visited[a-1] = 0
            if C[b-1] == k:
                ans[i] = 1
                C[a-1] = 1
                C[b-1] = 1
            else:
                ans[i] = C[b-1]+1
                C[b-1]+=1
                C[a-1] = C[b-1]
                
for a in ans:
    print(a)

Solution (Python):
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]
ans = {}
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    ans[(a, b)] = 0
    tmp.append((a, b))  


visited = [False]*N
colors = [-1]*N  
q = deque([0])  
visited[0] = True
while len(q):
    
    v = q.pop()
    color = 1

    for e in tree[v]:
        if visited[e]:  
            continue
        visited[e] = True
        if colors[v] == color:  
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

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

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

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

k = max(map(len, G))
print(k)

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

Solution (Python):
import sys
sys.setrecursionlimit(500000)

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

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

res = [-1 for _ in range(N-1)]
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dfs(child,v,col)
            col += 1
dfs()
print("\n".join(map(str, res)))

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())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append([b, i+1])
    tree[b].append([a, i+1])

edge = [0] * n 
visit = [False] * (n+1) 
color = [set() for i in range(n+1)]
visit[1] = True
q = [1]
edge[1] = 1

while q:
    now = q.pop()
    c = 1
    for next, num in tree[now]:
        if not visit[next]:
            while c in color[now]:
                c += 1
            edge[num] = c
            color[next].add(c)
            visit[next] = True
            q.append(next)
            c += 1
    before = now

print(max(edge))
for i in range(1, n):
    print(edge[i])