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 Counter
from collections import deque
INF = 1145141919810364364334
n = int(input())
c = []
b = [0] * (n-1)
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b[i] = map(int,input().split())
    edge[a-1].append(b[i]-1)
    edge[b[i]-1].append(a-1)
    c.append(a)
    c.append(b[i])

d = Counter(c)
hen = d.most_common()[0][1]

col = [INF] * n
col[0] = 0

q = deque()
q.append(0)

while q:
    x = q.popleft()
    no = (col[x] + 1) % hen
    for i in edge[x]:
        if col[i] == INF:
            col[i] = no
            no = (no+1) % hen 
            q.append(i)
            
print(hen)
for i in range(n-1):
    print(col[b[i]-1] + 1)

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

n = int(input())
g = [[] for _ 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 dfs(now, color):
    cnt = 1
    for to, num in g[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep='\n')

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)

dfs(0, -1)

print(max(colors.values()))
for a, b in ab:
    print(colors[(a, b)])

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

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

Solution (Python):

import sys
sys.setrecursionlimit(100000)
a_max = 0
class Node:
    def __init__(self):
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c


def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node() for _ in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    

    def s_node(node_num, prev_c):
        global a_max
        el = nodes[node_num-1].edge

        
        if len(el)>0:
            if prev_c not in range(1,len(el)+1):
                c_list = range(1,len(el)+1)
                a_max = max(a_max, len(el))
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
                a_max = max(a_max, len(el)+1)
            
            

            for node_n, c_ in zip(el, c_list):
                
                nodes[node_num-1].co_edge(node_n, c_) 
                
                nodes[node_n-1].rm_edge(node_num) 
                s_node(node_n, c_)

    s_node(1,0)

    print(a_max)
    
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans = (nodes[ai-1].color[bi])
        else:
            ans = (nodes[bi-1].color[ai])
        print(ans)
    
    


    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):
from sys import stdin
from collections import defaultdict
from collections import deque
 
N = int(stdin.readline().rstrip())
adj = defaultdict(set)
edges = []

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    edges.append((a,b))
    
visited = [False]*(N+1)
color_edges = defaultdict(bool)
visit_p = deque()
visit_p.append((1,0))
 
while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        color_edges[(node,i)] = cnt
        visit_p.append((i,cnt))
print(max(color_edges.values()))
for i in edges:
    if not color_edges[i]:
        print(color_edges[(i[1],i[0])])
    else:
        print(color_edges[i])

Solution (Python):
N=int(input())
import sys
sys.setrecursionlimit(10**6)
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  G[a-1].append((i,b-1))
  G[b-1].append((i,a-1))
ans=[0]*(N-1)  
def dfs(now_node,pre_node,pre_c):
  color=1
  
  for t in G[now_node]:
    num,next_node=t
    if next_node==pre_node:
      continue
    next_color=color
    if next_color==pre_c:
      next_color+=1
    ans[num]=next_color
    
    dfs(next_node, now_node,next_color)
    color=next_color+1
dfs(0,-1,-1)
print(max(ans))
for a in ans:
  print(a)

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

N=int(input())
G=[[] for _ 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 dfs(now,color):
  cnt=1
  for to,j in G[now]:
    if cnt==color:
      cnt+=1
    ans[j]=cnt
    dfs(to,cnt)
    cnt+=1

dfs(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 _ 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 dfs(now, color):
  cnt = 1
  for to, j in G[now]:
    if cnt == color:
      cnt += 1
    ans[j] = cnt
    dfs(to, cnt)
    cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep="\n")

Solution (Python):


from collections import deque


N = int(input())
node_list = {} 
color_count_list = [0]*(N+1)
ans_list = []
for i in range(N-1):
    a, b = map(int, input().split())
    if a in node_list:
        node_list[a].append(b)
    else:
        node_list[a] = [b]
    color_count_list[a] += 1
    color_count_list[b] += 1
    ans_list.append([a, b])


color_list = {}
color_max_count = max(color_count_list)


visit_queue = deque([[-1, 1]]) 
while len(visit_queue)>0:
    p = visit_queue.popleft()

    used_color = p[0]
    if p[1] in node_list:
        nodes = node_list[p[1]]
        nodes_len = len(nodes)
        color_num = 1
        if nodes_len>=1:
            coloring_count = 0
            while coloring_count<nodes_len:
                if color_num==used_color:
                    color_num += 1
                    continue
                
                if p[1] in color_list:
                    color_list[p[1]][nodes[coloring_count]] = color_num
                else:
                    color_list[p[1]] = {nodes[coloring_count]:color_num}
                if nodes[coloring_count] in color_list:
                    color_list[nodes[coloring_count]][p[1]] = color_num
                else:
                    color_list[nodes[coloring_count]] = {p[1]:color_num}
                
                visit_queue.append([color_num, nodes[coloring_count]])
                
                coloring_count += 1
                color_num += 1


print(color_max_count)
for a in ans_list:
    print(color_list[a[0]][a[1]])

Solution (Python):
from collections import deque

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

que=deque([0])
while que:
   s=que.pop()
   color=1
   for ni in G[s]:
      if ans[s]==color:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Solution (Python):
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
E = {}
A = []
for _ in range(N-1):
    a,b = map(int,input().split())
    A.append((a,b))
    G[a].append(b)
    G[b].append(a)
    E[(a,b)] = 0
hist = [0 for _ in range(N+1)]
heap = deque([1])
c = 1
for y in G[1]:
    E[(1,y)]=c
    c += 1
K = c-1
hist[1]=1
while heap:
    x = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            K = max(K,len(G[y]))
            col = [0 for _ in range(min(K,len(G[y]))+1)]
            for z in G[y]:
                if y<z and E[(y,z)]<len(col):
                    col[E[(y,z)]]=1
                elif z<y and E[(z,y)]<len(col):
                    col[E[(z,y)]]=1
            cur = 1
            for z in G[y]:
                if y<z and E[(y,z)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(y,z)]=i
                            cur = i+1
                            break
                elif z<y and E[(z,y)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(z,y)]=i
                            cur = i+1
                            break
            heap.append(y)
            hist[y]=1
print(K)
for e in A:
    print(E[e])

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

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

color = {}    
from collections import deque
q = deque([(0, 0)])
while len(q) > 0:
    src, c_prev = q.popleft()
    c = 1
    for dst in graph[src]:
        if c == c_prev: c += 1
        key = '{0}-{1}'.format(min(src, dst), max(src, dst))
        if color.setdefault(key, 0) == 0:
            color[key] = c
            q.append((dst, c))
            c += 1

print(max(color.values()))
for ai, bi in ab:
    key = '{0}-{1}'.format(min(ai, bi) - 1, max(ai, bi) - 1)
    print(color[key])

Solution (Python):
from collections import deque
import collections
n = int(input())
edge = []
cl = dict()
edge_ar = []
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    edge_ar.append((a,b))

q = deque([(0,1)])
used = set()
used.add(1)
while q:
    this = q.popleft()
    pre = this[0]
    here = this[1]
    k = 1
    for i in edge[here]:
        if i not in used:
            while True:
                if k != pre:
                    cl[(i,here)] = k
                    cl[(here,i)] = k
                    k += 1
                    break
                else:
                    k += 1
            used.add(i)
            q.append((k-1,i))
cl_num = collections.Counter(cl)
cl_num = max(list(cl_num.values()))
print(cl_num)
for i in edge_ar:
    print(cl[i])

Solution (Python):
N=int(input())
G=[[] for _ 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))
    G[b].append((a,i))

ans=[-1]*(N-1)
cmx=0
stk=[0]
while stk:
    v=stk.pop()
    cs=set()
    for to,toi in G[v]:
        if ans[toi]>=0: cs.add(ans[toi])
    c=1
    for to,toi in G[v]:
        if ans[toi]>=0: continue
        while c in cs: c+=1
        ans[toi]=c
        cmx = max(cmx, c)
        cs.add(c)
        stk.append(to)

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

Solution (Python):
N = int(input())
edges = [[] for _ in range(N)]

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

ans = [-1] * (N - 1)
st = [(0, -1)]
while st:
    now, pr = st.pop()

    C = []
    D = set()
    for i, _ in edges[now]:
        D.add(ans[i])
    for i in range(len(edges[now]) + 1)[::-1]:
        if i in D:
            continue
        C.append(i)

    for i, to in edges[now]:
        if to == pr:
            continue
        ans[i] = C.pop()
        st.append((to, now))

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

Solution (Python):
n=int(input())
edge=[[]for _ in range(n)]
point=[0]*n
edges=[]
point_color=[-1]*n
edge_color={}
edge_to_int=lambda x,y:min(x,y)*100007+max(x,y)
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges.append((a,b))
  edge[a].append(b)
  edge[b].append(a)
  point[a]+=1
  point[b]+=1
ans=max(point)
ind=point.index(ans)
Q=[ind]
visited={ind}
while Q:
  P=[]
  for i in Q:
    color=0
    for j in edge[i]:
      if j in visited:continue
      visited.add(j)
      P.append(j)
      color+=1
      if point_color[i]==color:color+=1
      point_color[j]=color
      edge_color[edge_to_int(i,j)]=color
  Q=P
print(ans)
for a,b in edges:
  print(edge_color[edge_to_int(a,b)])

Solution (Python):
from queue import deque

N = int(input())

A = []
B = [[]for i in range(N)]

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

q = deque([0])
color = [-1]*N
ans = {}
saidai = 0
while q:
    nord = q.popleft()
    c = 0
    for i, v in enumerate(B[nord]):
        if color[nord] == i:
            c += 1
        color[v] = c + i 
        ans[(nord, v)] = c + i
        q.append(v)
        saidai = max(saidai,i+c+1)

print(saidai)

for i, j in A:
    print(1+ans[(i-1, j-1)])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    dfs(u,v,k)
    k+=1
dfs(0)
for c in l: print(c)

Solution (Python):
from collections import deque

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

edges = [[]for _ in range(n)]
for x, y in e_list:
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)


q = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
q.append(0)
eColor_dic = {}
max_color = 0

while q:
    here = q.popleft()
    color = 1
    for i in edges[here]:
        if visited[i]:
            continue
        q.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        eColor_dic[(here, i)] = color
        color_list[i] = color
        max_color = max(max_color, color)
        color += 1

print(max_color)
for x, y in e_list:
    print(eColor_dic[(x-1, y-1)])

Solution (Python):
from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])

v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)

v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
path = sorted(path, key=lambda x: x[1])
path.sort(key=lambda x: x[0])
    
    
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])

Solution (Python):
from collections import deque, defaultdict

N = int(input())

connect_dic = defaultdict(list)

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

    connect_dic[a].append(b)
    connect_dic[b].append(a)


dq = deque([])
dq.append(a)

color_dic = defaultdict(set)
used_set = set()

comp = defaultdict(int)
max_ = 0

while dq:
    n = dq.popleft()

    can = connect_dic[n]
    l = len(can)
    max_ = max(max_, l)

    a_color = color_dic[n]

    num = 0
    for c in can:
        if c in used_set:
            continue

        while num in a_color:
            num += 1

        color_dic[n].add(num)
        color_dic[c].add(num)
        a_color.add(num)
        comp[(n, c)] = num
        comp[(c, n)] = num

        if c not in used_set:
            dq.append(c)

    used_set.add(n)

print(max_)
for a, b in edge:
    print(comp[(a, b)] + 1)

Solution (Python):
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Solution (Python):
from queue import deque

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
li = [[] for _ in range(n)]

for i,j in l:
    i,j = i-1,j-1
    li[i].append(j)
    li[j].append(i)

stack = 0
color = [0]*n

work_queue = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
work_queue.append(stack)
path = {}
ma = 0
while work_queue:
    here = work_queue.popleft()
    color = 1
    for i in li[here]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        path[(here,i)] = color
        color_list[i] = color
        ma = max(ma,color)
        color += 1

print(ma)
for i,j in l:
    i,j = i-1,j-1
    print(path[(i,j)])

Solution (Python):
from queue import deque

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
li = [[] for _ in range(n)]

for i,j in l:
    i,j = i-1,j-1
    li[i].append(j)
    li[j].append(i)

stack = 0
color = [0]*n

work_queue = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
work_queue.append(stack)
path = {}
ma = 0
while work_queue:
    here = work_queue.popleft()
    color = 1
    for i in li[here]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        path[(here,i)] = color
        color_list[i] = color
        ma = max(ma,color)
        color += 1

print(ma)
for i,j in l:
    i,j = i-1,j-1
    print(path[(i,j)])

Solution (Python):
from collections import deque 
import sys 
input = sys.stdin.readline 
n=int(input())
child= [[] for _ in range(n)]
edge_order =[]
for i in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1, b-1 
    child[a].append((i,b))
    edge_order.append(b)

queue=deque([0])
color=[0]*n 
while queue:
    v = queue.popleft()
    c = 1
    for i,u in child[v]:
        if c==color[v]:
            c+=1
        color[u]=c
        c+=1
        queue.append(u)
print(max(color))
for i in edge_order:
    print(color[i])

Solution (Python):
from collections import deque

N = int(input())
edges = []
nb = [[] for _ in range(N)]
maxdeg = 0
root = None
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((min(a, b), max(a, b)))
    nb[a].append(b)
    nb[b].append(a)
    if len(nb[a]) > maxdeg:
        maxdeg = len(nb[a])
        root = a
    if len(nb[b]) > maxdeg:
        maxdeg = len(nb[b])
        root = b

colors = {}
for i, x in enumerate(nb[root]):
    colors[x, root] = colors[root, x] = i + 1
    q = deque([(x, root, i + 1)])
    while q:
        node, parent, pcolor = q.popleft()
        colors[node, parent] = colors[parent, node] = pcolor
        color = 0
        for c in nb[node]:
            if c != parent:
                color += 1
                if color == pcolor:
                    color += 1
                q.append((c, node, color))

print(maxdeg)
for a, b in edges:
    print(colors[a, b])

Solution (Python):
N = int(input())
edges = []
nb = [[] for _ in range(N)]
maxdeg = 0
root = None
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((min(a, b), max(a, b)))
    nb[a].append(b)
    nb[b].append(a)
    if len(nb[a]) > maxdeg:
        maxdeg = len(nb[a])
        root = a
    if len(nb[b]) > maxdeg:
        maxdeg = len(nb[b])
        root = b

colors = {}
done = [False] * N
done[root] = True
for i, x in enumerate(nb[root]):
    colors[x, root] = colors[root, x] = i + 1
    stack = [(x, root, i + 1)]
    while stack:
        node, parent, pcolor = stack.pop()
        if done[node]:
            continue
        done[node] = True
        colors[node, parent] = colors[parent, node] = pcolor
        color = 0
        for c in nb[node]:
            if c != parent and not done[c]:
                color += 1
                if color == pcolor:
                    color += 1
                stack.append((c, node, color))

print(maxdeg)
for a, b in edges:
    print(colors[a, b])

Solution (Python):
from queue import Queue

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

color = {}


queue = Queue()
dist = [-1] * n
queue.put((-1, 0))  
dist[0] = 0
K = 1

while True:
    num, node = queue.get()
    next_nodes = edges[node]
    tmp_color = 1
    for next_node in next_nodes:
        if dist[next_node] != -1:
            continue
        dist[next_node] = dist[node] + 1

        if tmp_color == num:
            tmp_color += 1
        color[(node, next_node)] = tmp_color
        color[(next_node, node)] = tmp_color
        if tmp_color > K:
            K = tmp_color

        queue.put((tmp_color, next_node))
        tmp_color += 1

    if queue.empty():
        break

print(K)
for edge in edges_original:
    print(color[edge])

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

graph = [[] for _ in range(N+1)]
graph[0] = [0]
edct = {}
par = [-1] * (N+1)
par[1] = 0

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)
    edct[(a, b)] = 0

nmax = 0

for i, g in enumerate(graph[1:], 1):
    nmax = max(nmax, len(g))
    clr = 1
    for j in g:
        if par[j] != -1: continue
        if clr == par[i]:clr += 1
        edct[(min(i, j), max(i, j))] = clr
        par[j] = clr
        clr += 1

print(nmax)
for a, b in ab:
    print(edct[(a, b)])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
child = [[] for _ in range(n)]
edge_order = []
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1 
    child[a].append((i, b))
    edge_order.append(b)

queue = deque([0])
color = [0] * n
while queue:
    v = queue.popleft()
    c = 1 
    for i, u in child[v]: 
        if c == color[v]: 
            c += 1
        color[u] = c
        c += 1
        queue.append(u)

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

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

data = int(input())

array = [[] for i in range(data)]

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

result = [None]*(data-1)

def func(prt, col):
    cnt = 1
    for cld, org in array[prt]:
        if cnt==col:
            cnt += 1
        result[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

print(max(result))
for i in range(data-1):
    print(result[i])

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



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


color = [-1 for _ in range(N)]
ans= {}


stack = [0]
color[0] = 0
while stack:
  u = stack.pop()
  i = 1
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = i
      if color[v] == color[u]:
      	color[v] += 1
      	i += 1
      tmp = [u,v]
      tmp.sort()
      ans[tuple(tmp)] = color[v]
      i += 1

print(max(color))
for a,b in l:
  print(ans[(a,b)])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    g = [[] for _ in range(N)]
    edge_order = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append((i, b))
        edge_order.append(b)
    
    queue = deque([0])
    color = [0] * N
    while queue:
        v = queue.popleft()
        c = 1  
        for i, u in g[v]:
            if c == color[v]:  
                c += 1
            color[u] = c
            c += 1
            queue.append(u)
    print(max(color))
    for i in edge_order:
        print(color[i])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n = int(input())

G = defaultdict(lambda:[])
li = [] 
for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    li.append((a, b))
    G[a].append(b)
    G[b].append(a)
parent = [0]*n 
color = [-1]*n 


order = []
def dfs():
    parent[0] = -1
    stack = []
    u = 0
    stack.append(u)
    while stack:
        x = stack.pop()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            parent[v] = x
            stack.append(v)

dfs()


for x in order:
    temp = color[x]
    c = 1
    for y in G[x]:
        if y == parent[x]:
            continue
        if c == temp:
            c += 1
        color[y] = c
        c += 1
        
answer = []
for a, b in li:
    if parent[a] == b:
        answer.append(color[a])
    else:
        answer.append(color[b])

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

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


n = int(input())
g = [[] for _ 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))
    g[b].append((a, i))
ans = [0] * (n-1)


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


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

Solution (Python):

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


from collections import deque, defaultdict
def bfs(G, v, p):
    q=deque()
    q.append((v, p, 0))

    while q:
        
        V, P, C = q.popleft()
        next_color = 1 if C != 1 else 2
        for next_v in G[V - 1]:
            if next_v == P:continue
            if next_color == C:next_color += 1

            q.append((next_v, V, next_color))
            color[(V, next_v)] = next_color
            next_color += 1


n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n - 1)]
color = defaultdict(lambda :1)

G = Graph(ab)

color_num = 0
for i in G:
    temp = len(i)
    if temp > color_num:color_num = temp

print(color_num)
bfs(G, 1, -1)

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

Solution (Python):
import sys
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
from collections import deque
l=[0]*(n-1)
q=deque([0])
b=[1]+[0]*(n-1)
while q:
  v=q.pop()
  c=-1
  k=1
  for u,e in g[v]:
    if b[u]: c=l[e]
  for u,e in g[v]:
    if b[u]: continue
    if k==c: k+=1
    l[e]=k
    k+=1
    q.appendleft(u)
    b[u]=1
for c in l: print(c)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
tree=[[] for _ in range(N)]
ans=[-1]*(N-1)
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append((b-1,i))
    tree[b-1].append((a-1,i))
    
def dfs(now,prev=-1,color=0):
    color_num=1
    for i,j in tree[now]:
        if i==prev:
            continue
        if color_num==color:
            color_num=color_num+1
        ans[j]=color_num
        dfs(i,now,color_num)
        color_num=color_num+1

dfs(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 _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    dfs(u,v,k)
    k+=1
dfs(0)
for c in l: print(c)