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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    G = [[] for _ in range(N)]
    edges = []
    edge2color = {}
    for _ in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
        edges.append((a, b))
    K = -1
    for adj_v in G:
        K = max(K, len(adj_v))
    visited = [0] * N
    def colorGraph(v, parColor=-1):
        children = G[v]
        colorNum = 1
        visited[v] = 1
        for child_v in children:
            if visited[child_v]:
                continue
            if colorNum == parColor:
                colorNum += 1
            edge2color[(v, child_v)] = colorNum
            edge2color[(child_v, v)] = colorNum
            colorGraph(child_v, colorNum)
            colorNum += 1
    
    
    colorGraph(0)
    print(K)
    for edge in edges:
        key = (edge[0], edge[1])
        print(edge2color[key])

main()

Solution (Python):

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

v_color = [0] * N
e_color = [0] * (N-1)
K = 1
for a, children in enumerate(G):
    c = 1
    for b, i in children:
        if c == v_color[a]:
            c += 1
        v_color[b] = c
        e_color[i] = c
        K = max(K, c)
        c += 1

print(K)
print('\n'.join(map(str, e_color)))

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
A=[]
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    A.append((a,b))

P=[-1 for i in range(N+1)]
P[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(N):
    if len(Q)==i:
        break
    P[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if P[j]==-1:
            Q.append([j,Q[i][0]])


D={}
D[(0,1)]=0
cnt=1
p=0
for i in range(N-1):
    if p!=Q[i][1]:
        p=Q[i][1]
        cnt=1
        for j in range(cnt,10**6):
            if D[(min(Q[i][1],P[Q[i][1]]),max(Q[i][1],P[Q[i][1]]))] != j:
                D[(min(Q[i]),max(Q[i]))] = j
                cnt = j+1
                break
    else:
        for j in range(cnt,10**6):
            if D[(min(Q[i][1],P[Q[i][1]]),max(Q[i][1],P[Q[i][1]]))] != j:
                D[(min(Q[i]),max(Q[i]))] = j
                cnt = j+1
                break
print(max(D.values()))
for i in range(N-1):
    print(D[A[i][0],A[i][1]])

Solution (Python):

import sys
from collections import deque
from collections import defaultdict
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))


def solve(N: int, a: "List[int]", b: "List[int]"):

    g = Graph(N)
    for i, (aa, bb) in enumerate(zip(a, b)):
        g.add_edge(aa-1, bb-1, i)

    visited = [False]*N
    edge_color = [-1]*(N-1)

    q = deque([(0, -1)])

    while len(q) > 0:
        node, color = q.popleft()
        penki = 1
        if color == penki:
            penki += 1

        for to_, weight in g.E[node]:
            if edge_color[weight] != -1:
                continue
            edge_color[weight] = penki
            q.append((to_, penki))
            penki += 1
            if color == penki:
                penki += 1

    print(max([len(g.E[k]) for k in g.E]))
    print(*edge_color, 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
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):
n = int(input())
G = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    d[(a,b)] = d[(b,a)] = i

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

stack = [(0,-1)] 

while stack:
    now,pre = stack.pop()
    color = 1
    for nex in G[now]:
        if nex == pre:continue
        stack.append((nex,now))
        if pre != -1:
            if color == ans[d[(now,pre)]]:
                color += 1
        ans[d[(now,nex)]] = color
        k = max(k,color)
        color += 1

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

Solution (Python):
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
G = [[] for _ in range(N)]
E = {}

for i in range(N-1):
  a, b = ints()
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)
  E[(a, b)] = i

C = [0]*(N-1)
S = [(0, None, None)]
max_color = 0
while len(S)>0:
  node, from_node, from_color = S.pop()

  c = -1
  for n in G[node]:
    if n==from_node:
      continue
    c += 1
    if c==from_color:
      c += 1

    max_color = max(max_color, c)
    C[E[(min(n, node), max(n, node))]] = c
    S.append((n, node, c))

print(max_color+1)
for i in C:
  print(i+1)

Solution (Python):
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for u, i in next_v:
        
        if ans[i] > 0:
            continue
        
        if cnt == c_p:
            cnt += 1
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

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

Solution (Python):
from collections import deque

N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

"""
bfs pattern
"""
q = deque()
next_v = edges[0]
for c, (u,i) in enumerate(next_v):
    q.append((u, i, c+1))
    ans[i] = c+1

while q:
    u_p, _, c_p = q.popleft()
    next_v = edges[u_p]
    cnt = 1
    for j, (u, i) in enumerate(next_v):
        
        if ans[i] > 0:
            continue
        
        if cnt == c_p:
            cnt += 1
        ans[i] = cnt
        q.append((u,i,cnt))
        
        cnt += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)
N = int(input())
edges = [[] for i in range(N)]
e_list = []

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

ans = [0] * (N-1)

def dfs(v, p=-1, c=-1): 
    
    global ans
    next_v = edges[v]
    cnt = 1 
    for u,i in next_v:
        
        if u == p: continue
        
        if cnt == c:
            cnt += 1
        ans[i] = cnt      
        cnt += 1
        dfs(u, v, ans[i])


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

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

n = int(input())
es = [[] for _ in range(n)]

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

ans = [0] * (n-1) 

def coloring(vi,prev_color):
  color = 1    
  for to,i in es[vi] :
    if color == prev_color:
      color += 1        
    ans[i] = color     
    coloring(to,color)
    color += 1
    
coloring(0,0)

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

Solution (Python):
















import sys
sys.setrecursionlimit(1000000)
from collections import deque



class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    
    def childnum(self):
        return len(self.child)

    


class Tree():
    
    
    
    def __init__(self):
        self.tree=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        self.edge=[]
        for i in range(self.node_n-1):
            self.edge.append([int(j) for j in input().split()])
        copyedge=sorted(self.edge)
        checkedge=deque()
        for edge in copyedge:
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1 or first.name==0:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
                
        while checkedge:
            edge=checkedge.popleft()
            first=self.tree[edge[0]-1]
            second=self.tree[edge[1]-1]
            if first.parent!=-1:
                first.child.append(second)
                second.parent=first
            elif second.parent!=-1:
                second.child.append(first)
                first.parent=second
            else:
                checkedge.append(edge)
       
     
    
    def getroot(self):
        return self.tree[0]
    
    
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


N = int(input())

es = [[] for _ in range(N)]


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


ans = [0] * (N-1)


def solve(now, prev_color):
    
    color = 1
    for b,i in es[now]:
        
        if color == prev_color:
            color += 1
        
        ans[i] = color
        
        solve(b, color)
        
        color += 1


solve(0,0)



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

Solution (Python):

def dfs_deep_measure(st, n, reach, color):
    ans_list = [[0, 0, 0, 0, 0] for i in range(n)]
    
    stack = [st]
    ans_list[st][0] = 1
    ans_list[st][1] = -1
    ans_list[st][2] = -1
    ans_list[st][3] = st
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        c = ans_list[tmp][1]
        for i, j in tmp_list:
            if ans_list[i][0] != 1:
                stack.append(i)
                ans_list[i][0] = 1
                c += 1
                ans_list[i][1] = c % color
                ans_list[i][2] = tmp
                ans_list[i][3] = i
                ans_list[i][4] = j
    return ans_list


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

st = -1
color = -1
for i in range(n):
    if len(reach[i]) > color:
        color = len(reach[i])
        st = i




ans_list = dfs_deep_measure(st, n, reach, color)
ans_list.sort(key=lambda x: x[4])


print(color)
for i in range(len(ans_list)):
    if ans_list[i][1] == -1:
        pass
    else:
        print(ans_list[i][1]+1)

Solution (Python):
















import sys
sys.setrecursionlimit(1000000)




class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.color=0
        
        
        
        
    
    def childnum(self):
        return len(self.child)

    


class Tree():
    
    
    
    def __init__(self):
        self.tree=[]
        self.edge=[]
        self.node_n=int(input())
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.edge.append(edge)
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    
    def getroot(self):
        return self.tree[0]
    
    
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    
    def gettree(self):
        return self.tree[:]

    
    
    
    
    
tree=Tree()

ans=0
node=tree.getroot()


def dps(Node):
    global ans
    colorlist=[]
    p_col=Node.color
    childnum=Node.childnum()
    for i in range(childnum+1):
        colorlist.append(i+1)
    if p_col in colorlist:
        colorlist.remove(p_col)
    else:
        colorlist.pop()
    
    if colorlist!=[]:
        maxcol=colorlist[-1]
        if maxcol>=ans:
            ans=maxcol
        children=Node.child
        for i in range(childnum):
            children[i].color=colorlist[i]
        for child in children:
            dps(child)
    

dps(node)

print(ans)

tre=tree.gettree()
edge=tree.edge
n=tree.node_n

for i in edge:
    print(tre[i[1]-1].color)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n = inp()
    g = [[] for _ in range(n)]
    color = [0 for _ in range(n)]
    did = [0 for _ in range(n)]
    dic = defaultdict(str)
    p = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        g[b].append(a)
        g[a].append(b)
        if a<b:
            a,b = b,a
        key = [str(a)]
        key.append(' ')
        key.append(str(b))
        key = ''.join(key)
        p.append(key)
        dic[key] = 1
    que = deque([])
    did[0]=1
    que.append(0)
    ans = 0
    while que:
        start = que.pop()
        go = g[start]
        c = 1
        for i in range(len(go)):
            t = go[i]
            if did[t]:
                continue
            else:
                if c == color[start]:
                    c += 1
                did[t] = 1
                que.append(t)
                color[t] = c
                ans = max(ans,c)
                key = []
                x = start
                y = t
                if x<y:
                    x,y = y,x
                key.append(str(x))
                key.append(' ')
                key.append(str(y))
                key = ''.join(key)
                dic[key] = c
                c += 1
    print(ans)
    for i in range(n-1):
        key = p[i]
        print(dic[key])

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
AB = [list(map(int, 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)


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

while stack:
  s = stack.pop()
  order.append(s)
  for g in graph[s]:
    if parent[s] == g:
      continue
    else:
      parent[g] = s
      stack.append(g)



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

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


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

Solution (Python):
N = int(input())
d = {}
E = [[] for _ in range(N)]

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


q = [(0,-1)]

while q:
    node,p = q.pop()
    col = 1
    for to in E[node]:
        if to!=p:
            q.append((to,node))
            if p!=-1:
                if col==ans[d[(node,p)]]:
                    col+=1
            ans[d[(node,to)]]=col
            K=max(K,col)
            col+=1

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

Solution (Python):

import sys
input = sys.stdin.readline

N = int(input())
E=[[] for _ in range(N)]

index ={}

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

K=0

ans=[None]*(N-1)



Q=[(0,-1)]
while(Q):
    node,p=Q.pop()
    col=1
    
    if p==-1:
        for to in E[node]:
            
            ans[index[(node,to)]]=col
            col +=1
            K=max(col,K)
            Q.append((to,node))
    
    else:
        for to in E[node]:
            if to==p:
                continue
            
            col+=(col==ans[index[(node,p)]]) 
            ans[index[(node,to)]]=col
            col+=1
            K=max(col,K)
            Q.append((to,node))

print(K-1)
print(*ans,sep="\n")

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

n = int(input())

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

    
ans = [0]*(n-1)

def col(now,color):
    c = 1
    for (b,j) in graph[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b,c)
        c += 1

col(0,0)
print(max(ans))
for a in ans:
    print(a)

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, list(input().split()))
    edges[a-1].append((b-1, i))


ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)


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

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

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == res[e][prev_edge]:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])

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

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1,prev_color=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == prev_color:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e,cnt)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])

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

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1,prev_color=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == prev_color:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e,cnt)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])

Solution (Python):
from collections import deque

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

colors = [-1] * N

q = deque([0])

while len(q) != 0:
    v = q.popleft()  
    color = 1
    for e in tree[v]:  
        if colors[e] != -1:
            continue
        if color == colors[v]:
            color += 1
        colors[e] = color
        tmp[v, e] = color
        color += 1
        q.append(e)
print(max(colors))



for a, b in saigen:
    print(tmp[a, b])

Solution (Python):
from collections import defaultdict, deque

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



root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

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

Solution (Python):
N = int(input())

edges = [[] for i in range(N+1)]
el = []
ecol = {}

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


queue = [[1,0]]
while(len(queue) != 0):
    
    p = queue.pop(0)
    p_el = edges[p[0]]
    c = 1
    for v in p_el:
        key1 = "{},{}".format(p[0],v)
        key2 = "{},{}".format(v,p[0])
        
        if (not(key1 in ecol)) :
            
            if (c == p[1]):
                c += 1
            ecol[key1] = c
            ecol[key2] = c
            queue.append([v,c])
            c += 1

print(max(ecol.values()))
for i in range(N-1):
    print(ecol[el[i]])

Solution (Python):

from collections import deque

n = int(input())
E = [[] for _ 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)


q = deque([1])
color = [0] * (n+1) 
while q:
    V = q.popleft()
    c = 1
    for nv in E[V]:
        if c == color[V]:
            c += 1
        color[nv] = c
        c += 1
        q.append(nv)

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

Solution (Python):
N = int(input())
edge = []

d_col = [0] * N

e_col = [1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    edge.append([a, b, i, 0])
edge = sorted(edge)
for j, e in enumerate(edge):
    a, b, i, ans = e
    if d_col[a-1] == e_col[a-1]:
        edge[j][3] = e_col[a-1] + 1
        e_col[a-1] += 1
    else:
        edge[j][3] = e_col[a-1]
    d_col[b-1] = e_col[a-1]
    e_col[a-1] += 1
edge = sorted(edge, key=lambda x: x[2])
col = []
for e in edge:
    col.append(e[3])
print(max(col))
for i in col:
    print(i)

Solution (Python):
from sys import stdin

input = stdin.buffer.readline

n = int(input())
v = [[] for _ in range(n+1)]
edge = [0] * -~n

ans = 0


def dfs(c,fa,x):
    global ans
    color = 1
    for to, eg in v[x]:
        if to == fa:
            continue
        if color == c:
            color += 1
        edge[eg] = color
        ans = max(ans, color)
        dfs(color, x, to)
        color += 1


def bfs(x):
    q = [[0,0,x]]
    ans = 0
    while len(q):
        c, fa, now = q.pop()
        color = 1
        for to, eg in v[now]:
            if to == fa:
                continue
            if color == c:
                color += 1
            edge[eg] = color
            q.append([color, now, to])
            ans = max(ans, color)
            color += 1
    return ans


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

print(bfs(1))
for i in range(n-1):
    print(edge[i])

Solution (Python):
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append((b,i+1))
    dst[b].append((a,i+1))

narcs = [len(x) for x in dst]
mx = max(narcs)
for i in range(n):
    if narcs[i]==mx:
        mxi = i
        break

color = [-1]*n
color[dst[mxi][0][1]] = 0
q = [mxi, dst[mxi][0][0]]
while len(q)>0:
    p = q.pop()
    for i in range(len(dst[p])):
        arc = dst[p][i][1]
        if color[arc] != -1:
            c = color[arc]
            arc0 = arc
            break
    for i in range(len(dst[p])):
        arc = dst[p][i][1]
        if arc==arc0:
            continue
        nd = dst[p][i][0]
        c = (c+1)%mx
        color[arc] = c
        q.append(nd)

print(mx)
for i in range(1,n):
    print(color[i]+1)

Solution (Python):
import math
import collections
import numpy as np


class Edge:
    def __init__(self, dst, color):
        self.dst = dst
        self.color = color

    def __repr__(self):
        return str(self.dst) + ' ' + str(self.color)


def main():
    N = int(input())
    adj_list = [[] for _ in range(N+1)]
    edge_order = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        edge_order.append((a, len(adj_list[a])))
        adj_list[a].append(Edge(b, None))
        adj_list[b].append(Edge(a, None))

    max_deg = 0
    for i in range(1, N+1):
        max_deg = max(max_deg, len(adj_list[i]))
    K = max_deg
    print(K)

    queue = collections.deque()
    queue.append((1, None))
    while queue:
        cur_node, used_color = queue.popleft()
        
        
        
        

        
        if used_color is None:
            color = 0
        else:
            color = (used_color + 1) % K
        for edge in adj_list[cur_node]:
            if edge.color is not None:
                pass
            else:
                edge.color = color
                for inv_edge in adj_list[edge.dst]:
                    if inv_edge.dst == cur_node:
                        inv_edge.color = color
                adj_list[edge.dst]
                queue.append((edge.dst, color))
                color = (color + 1) % K
        

    for i, j in edge_order:
        print(adj_list[i][j].color + 1)


if __name__ == '__main__':
    main()

Solution (Python):


import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    G = [[] for i in range(N)]
    ans = [None] * (N-1)
    
    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))
        
    q = [(0, -1)]
    
    visited = [False] * N
    cur = 0
    
    while q and cur < N:
        v, c = q.pop(0)
    
        if visited[v]: continue
        visited[v] = True
        cur += 1
        
        k = 0
        for u, idx in G[v]:
            if visited[u]: continue
            if c == k: k += 1
            
            ans[idx] = k
            q.append((u, k))
            k += 1
            
    print(max(ans)+1)
    for a in ans: print(a+1)
     
if __name__ == '__main__':
    main()