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
sys.setrecursionlimit(10**7)
n=int(input())
s=[[]for i in range(n+1)]
t=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    s[a-1].append([b-1,i])
def f(x,r):
    c=1
    for (i,j) in s[x]:
        c+=(c==r)
        t[j]=c 
        f(i,c)
        c+=1
f(0,0)
print(max(t))
for i in t:
    print(i)

Solution (Python):
def main():

    from collections import deque


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

    Q = deque([1])
    C = [0] * (N + 1)
    while Q:
        v = Q.popleft()
        c = 0
        for u in E[v]:
            c += 1 + (c + 1 == C[v])
            C[u] = c
            Q.append(u)

    print(max(C))
    print("\n".join(str(C[b]) for b in B))
main()

Solution (Python):
from collections import deque


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

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
print("\n".join(str(C[b]) for b in B))

Solution (Python):
import sys

sys.setrecursionlimit(100000)
n = int(input())
bfs_dic = [{} for i in range(n)]
ans = [0 for i in range(n-1)]

def bfs(pn, pc, node):
    c = 1
    max_c = 0
    
    if len(bfs_dic[node]) != 1 or pc == 0: 
        for k,v in bfs_dic[node].items():
            if k == pn: continue 
            if pc == c:                 
                c+=1
            ans[v] = c
            maxable_c = bfs(node, c, k)
            if max_c < maxable_c:
                max_c = maxable_c
            c+=1                        
        if max_c < c-1:
            return c-1
        else:
            return max_c
    return 1                                        
            
for i in range(n-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    bfs_dic[a][b] = i
    bfs_dic[b][a] = i

print(bfs(-1, 0, 0))
for i in ans:
    print(i)

Solution (Python):
import collections 
import sys
sys.setrecursionlimit(1000000)

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)

Solution (Python):
from collections import deque

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

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

visited = [False]*n
colors = [0]*(n-1)

max_colors = max(len(t) for t in T)
que = deque([(0,0)])


while que:
    node, p_color = que.popleft()
    visited[node] = True
    color = 1
    
    for nxt_n, nxt_e in T[node]:
        if visited[nxt_n] == True:
            continue
        if color == p_color:
            color += 1
        colors[nxt_e] = color
        que.append((nxt_n, color))
        color += 1

print(max_colors)
print(*colors, sep='\n')

Solution (Python):

N = int(input())
edges = [[] for _ in range(N+1)]


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

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

for a in ans:
  print(a)

Solution (Python):
'''input
6
1 2
1 3
1 4
1 5
1 6
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import defaultdict
import sys, threading


def get_source(graph):
	for i in graph:
		return i


def make(first, second):
	return str(first) + ' ' + str(second)


def dfs(graph, node, visited, color, medges, mx_c):
	visited[node] = True
	c = 1
	for i in graph[node]:
		if i not in visited:
			if color[node] == c:
				c += 1
			color[i] = c
			medges[make(node, i)] = c
			medges[make(i, node)] = c
			mx_c[0] = max(mx_c[0], c)
			c += 1
			dfs(graph, i, visited, color, medges, mx_c)



def main():
	graph = defaultdict(list)
	n = int(input().strip())
	edges = []
	for _ in range(n - 1):
		u, v = list(map(int, input().split()))
		graph[u].append(v)
		graph[v].append(u)
		edges.append([u, v])

	s = get_source(graph)
	color = dict()
	visited = dict()
	color[s] = 0
	medges = dict()
	mx_c =[0]
	dfs(graph, s, visited, color, medges, mx_c)

	print(mx_c[0])
	for i, j in edges:
		print(medges[make(i, j)])


if __name__ == '__main__':
	sys.setrecursionlimit(100005)
	threading.stack_size(1 << 27)
	thread = threading.Thread(target = main)
	thread.start()

Solution (Python):
from collections import deque

def edge_key(node1, node2):
    return '-'.join([str(min(node1, node2)), str(max(node1, node2))])

def bfs(si):
    q = deque()
    q.append([si, -1])
    used.add(si)

    while len(q) > 0:
        prv_node, prv_col = q.popleft()
        col = 1
        for node in g[prv_node]:
            if node in used:
                continue
            else:
                if col == prv_col:
                    col += 1

                cols[eds[edge_key(prv_node, node)]] = col
                q.append([node, col])
                used.add(node)
                col += 1

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

used = set()
cols = [-1 for _ in range(N-1)]
bfs(0)
print(max(cols))
[print(col) for col in cols]

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

dic = {}
color = {}
root = [0]*N

for i in range(N):
    dic[i+1] = []
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    dic[i].append(j)
    dic[j].append(i)
    root[i-1] += 1
    root[j-1] += 1
    color[(i,j)] = 0
root_node = root.index(1)+1
ma = max(root)
def rec(now_node,prevcolor):
    nowcolor = 0
    tg_list = dic[now_node][:]
    for elem in tg_list:
        nowcolor += 1
        if nowcolor == prevcolor:
            nowcolor += 1
        dic[elem].remove(now_node)
        color[(elem,now_node)] = nowcolor
        color[(now_node,elem)] = nowcolor
        rec(elem,nowcolor)
rec(root_node,0)
print(ma)
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    print(color[(i,j)])

Solution (Python):
from collections import deque

n=int(input()) 




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


ans=[0]*(n-1)
visit=[-1]*n
q=deque([0])
visit[0]=0

while q:
    v=q.popleft()
    count=1
    for x in edges[v]:
        if visit[x]<0:
            if count==visit[v]:
                count+=1
            q.append(x)
            visit[x]=count
            ans[l[(v,x)]]=count
            count+=1
            
print(max(ans))
for i in range(n-1):
    print(ans[i])

Solution (Python):
from collections import deque

n = int(input())

graph = [[] for _ in range(n)]

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

que = deque([(0, None)])
visited = [False] * n
visited[0] = True

edge = [{} for _ in range(n)]

color_n = -1
while que:
    now, skip = que.popleft()
    i = 0
    for t in graph[now]:
        if not visited[t]:
            if i == skip:
                i += 1
            que.append((t, i))
            visited[t] = True
            
            edge[now][t] = i + 1
            color_n = max(color_n, i + 1)
            i += 1

print(color_n)
for f, t in inputs:
    print(edge[f].get(t) or edge[t].get(f))

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

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab2 = [[] for i in range(n)]
for i in range(n-1):
  ab2[ab[i][0]-1].append([ab[i][1]-1, i])
  ab2[ab[i][1]-1].append([ab[i][0]-1, i])
coloring = [0]*(n-1)

def f(x, y, z):
  c = 0
  for i in ab2[x]:
    if i[0] != y:
      c += 1
      if c == z:
        c += 1
      coloring[i[1]] = c
      x1 = i[0]
      y1 = x
      z1 = c
      f(x1, y1, z1)

f(0, None, None)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])

Solution (Python):
def bfs(n,e,fordfs,D):
    
    W = [-1]*(n-1)
    
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[a[i] - 1].append((b[i] - 1, i))
        conns[b[i] - 1].append((a[i] - 1, i))
    k = 0
    for i in range(N):
        k = max(k, len(conns[i]))
    ret = [0] * (N - 1)
    def dfs(idx, prev, visited):
        visited[idx] = True
        color = 0 if prev != 0 else 1
        for node, idx in conns[idx]:
            if not visited[node]:
                ret[idx] = color + 1
                dfs(node, color, visited)
                color += 1
                if color == prev:
                    color += 1
    visited = [False] * N
    dfs(0, -1, visited)
    print(k)
    for r in ret:
        print(r)
    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 collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
K=max([len(i) for i in G])
print(K)
q=deque([])
q.append(0)
reached=[0 for i in range(N)]
parentsnum=[-1 for i in range(N)]
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    index=0
    if parentsnum[r]!=-1:
        index=(parentsnum[r]+1)%K
    for p in G[r]:
        if reached[p]==1:
            continue
        edges[(min(r,p),max(r,p))]=index
        parentsnum[p]=index
        index+=1
        index%=K
        q.append(p)
for i in range(N-1):
    print(edges[min(a[i],b[i]),max(a[i],b[i])]+1)

Solution (Python):
import queue
n = int(input())
tree_node = [set() for _ in range(n)]
hen = []
hen_col = {}
for i in range(n-1):
    a,b = map(int,input().split())
    tree_node[a-1].add(b)
    hen.append([a,b])
    hen_col[str(a)+'-'+str(b)] = 0
q = queue.Queue()
q.put(1)
parent_node = [0] * n
parent_color = [0] * n
maxcol = 0
while not q.empty():
    col = 0
    nod = q.get()
    for i,c in enumerate(tree_node[nod-1]):
        if i+1 == parent_color[nod-1]:col+=1
        tempcol = i+1+col
        parent_color[c-1]=tempcol
        maxcol = max(maxcol,tempcol)
        q.put(c)
        l = min(nod,c)
        r = max(nod,c)
        hen_col[str(l)+'-'+str(r)] = tempcol
        parent_node[c-1] = nod

print(maxcol)
for t in hen:
    tempstr = str(t[0])+'-'+str(t[1])
    print(hen_col[tempstr])

Solution (Python):
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
mp=[[] for i in range(N+1)]

for i in range(N-1):
    a,b=LI()
    mp[a].append((b, i))
    mp[b].append((a, i))

ma = 0
ma_e = 0
for i, arr in enumerate(mp):
    if len(arr) > ma:
        ma = len(arr)
        ma_e = i

CLS = [0]*(N-1)
VISITED = [0]*(N+1)
Q=deque([(ma_e, 0)])
VISITED[ma_e] = 1

while Q:
    v, c = Q.popleft()
    cnt = 0
    for next_e, i in mp[v]:
        if VISITED[next_e]: continue
        color = ((c + cnt) % ma) + 1
        CLS[i] = color
        

        Q.append((next_e, color))
        VISITED[next_e] = 1
        cnt += 1

print(ma)
for i in CLS: print(i)

Solution (Python):
from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    col = 1 
    for i in g[prvi]:
      if i in used:continue
      if col == prvcol: col += 1
      cols[eds[str(min(prvi,i))+'-'+str(max(prvi,i))]] = col
      q.append([i,col])
      used.add(i)
      col += 1

N = int(input())
g = {i:[] for i in range(N)}
eds = {}
for i in range(N-1):
  a,b = map(int,input().split())
  eds[str(a-1)+'-'+str(b-1)] = i
  g[a-1].append(b-1)
  g[b-1].append(a-1)

used = set([])
cols = [-1 for _ in range(N-1)]  
bfs(0)
print(max(cols))
[print(col) for col in cols]

Solution (Python):
from collections import deque
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a].append((b,i))
  edges[b].append((a,i))
ans=[0]*(n-1)
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:
  up,_,cp=q.popleft()
  next_v=edges[up]
  cnt=1
  for u,i in next_v:
    if ans[i]>0:
      continue
    if cnt==cp:
      cnt+=1
    ans[i]=cnt
    q.append((u,i,cnt))
    cnt+=1
print(max(ans))
for i in ans:
  print(i)

Solution (Python):
N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[min(v,P[v]),max(v,P[v])]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[min(u,v),max(u,v)]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)

Solution (Python):
from collections import deque

N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)

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

N=int(input())
ab=[list(map(int, input().split())) for i in range(N-1)]
link=[[] for i in range(N+1)]
for i in range(0, N-1):
  link[ab[i][0]].append([ab[i][1], i])
  link[ab[i][1]].append([ab[i][0], i])
  
out=[0]*(N-1)
def f(num, prenum=0, prec=0):
  postc=1
  for postnum, linknum in link[num]:
    if postnum==prenum:
      continue
    if postc==prec:
      postc+=1
      
    out[linknum]=postc
    f(postnum, num, postc)
    postc+=1
    
f(1)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
def colorize(current_node, adjacents, colors, from_color, k):
    
    
    count = 0
    for edge, node in adjacents[current_node]:
 
        
        if colors[edge]!=None:
            continue
        
        count += 1
        colors[edge] = (from_color+count)%k
        colorize(node, adjacents, colors, colors[edge], k)
     
N = int(input())
adjacents = {i+1:[] for i in range(N)}
 
for i in range(N-1):
    a,b = [int(e) for e in input().split(" ")]
    
    adjacents[a].append( [i+1,b] )
    adjacents[b].append( [i+1,a] )
 

most_edge =sorted(adjacents, key=lambda d:len(adjacents[d]))[-1]
k = len(adjacents[most_edge])
 
colors = {i+1:None for i in range(N-1)}
colorize(1, adjacents, colors, -1, k)
 
print(k)
for color in colors.values():
    print(color+1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    ab = [LI() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)
    t = sorted([(-len(e[i]), i) for i in range(1,n+1)])
    d = collections.defaultdict(set)
    r = {}
    for _, a in t:
        i = 1
        for b in e[a]:
            if (a,b) in r:
                continue
            while i in d[a] or i in d[b]:
                i += 1
            d[a].add(i)
            d[b].add(i)
            r[(a,b)] = r[(b,a)] = i
            i += 1
    rr = []
    for a,b in ab:
        rr.append(r[(a,b)])

    return JA([max(rr)] + rr, "\n")


print(main())

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):

import sys
sys.setrecursionlimit(10**5+10)

n = int(input())
visited = set()
g = {}
idx = {}
color = {}
for i in range(n-1):
    a,b = map(int, input().split())
    idx[i] = (a,b)
    if a not in g:
        g[a] = []
    g[a].append(b)
    if b not in g:
        g[b] = []
    g[b].append(a)

def dfs(v,c):
    cc = 0
    for u in g[v]:
        if u in visited:
            continue
        visited.add(u)

        cc += 1
        while cc==c:
            cc += 1
        a,b = min(u,v),max(u,v)
        color[(a,b)] = cc
        
        dfs(u,cc)
visited.add(1)
dfs(1,0)

mc = 0
for c in color.values():
    mc = max(mc, c)
print(mc)
for i in range(n-1):
    print(color[idx[i]])

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n = int(input())

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

ans = [None for _ in range(n-1)]
used = [False for _ in range(n)]
k = 0


def dfs(node, col=-1, parent=-1):
    global k
    if k < len(tree[node]):
        k = len(tree[node])

    c = 1
    for neighbor, i in tree[node]:
        if neighbor == parent:
            continue
        if c == col:
            c += 1
        ans[i] = c
        c += 1
        dfs(neighbor, ans[i], node)


dfs(0)

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

Solution (Python):
def main():
    n = int(input())
    
    cnt = [0] * n
    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))
        cnt[a-1] += 1
        cnt[b-1] += 1


    
    
    
    
    
    
    num = 0
    
    print(max(cnt))

    tmp_clr = [0] * (n-1)
    tmp_edge = [0] * n

    
    for frm, child in enumerate(G):
        clr = 1
        for j, to  in enumerate(child):

            if tmp_edge[frm] == clr :
                clr += 1
            tmp_clr[to[1]] = clr
            
            tmp_edge[to[0]] = clr
            clr+=1
    
    
    print('\n'.join(map(str, tmp_clr)))

if __name__=='__main__':
    main()

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

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
to_edges = [e[1] for e in edges] 

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

queue = deque([1])
colors = [0] * (n + 1)
while queue:
    x = queue.popleft()
    c = 0
    for y in tree[x]:
        c += 1 + (c + 1 == colors[x])
        colors[y] = c
        queue.append(y)

print(max(colors))
for e in to_edges:
    print(colors[e])

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

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]
B = [e[1] for e in edges] 

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

Q = deque([1])
C = [0] * (n + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Solution (Python):
from collections import deque
 
N, *AB = map(int, open(0).read().split())
B = AB[1::2]
 
E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

Solution (Python):
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque


"""
for each edge, keep track of parent, and each edges color
while we are BFSing, we can just iterate from 1, and skip if the next one is same as parents
"""


N = gi()
ecs = {}
nbls = [[] for i in range(N + 5)]  
p = [0] * (N + 5)
in_l = []

max_d = 0

for i in range(1, N):
    a = gi()
    b = gi()
    nbls[a].append(b)
    nbls[b].append(a)
    max_d = max(max_d, len(nbls[a]), len(nbls[b]))
    in_l.append((min(a, b), max(a, b)))
p[1] = 0  
ecs[(0, 1)] = -1

c_i = 0
q = deque()
q.append(1)

while len(q):
    v = q.pop()
    
    parent_ci = ecs[(min(v, p[v]), max(v, p[v]))]
    for u in nbls[v]:
        if u == p[v]:
            continue
        q.append(u)
        p[u] = v
        if parent_ci == c_i:
            c_i += 1
            c_i %= max_d
        ecs[(min(u, v), max(u, v))] = c_i
        c_i += 1
        c_i %= max_d

print(max_d)
for e in in_l:
    print(ecs[e] + 1)

Solution (Python):

import math
import fractions

def makeDivisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def makeNeighbor(es,n):
    nlist = [[] for i in range(n+1)]
    for i in es:
        nlist[i[0]].append(i[1])
        nlist[i[1]].append(i[0])
    return nlist
    



n = int(input())
es = []
for i in range(n-1):
    es.append(list(map(int, input().split())))
nb = [[] for i in range(n+1)]
ct = 0

for i in es:
    nb[i[0]].append([i[1],ct])
    nb[i[1]].append([i[0],ct])
    ct+=1

ans = [-1 for i in range(n-1)]
mx = 0
for i in nb:
    if mx<len(i) : mx = len(i)

que = [[1,0]]
end = [0 for i in range(n+1)]
done = 0
end[1]=1
while(len(que) > done):
    nowpos = que[done][0]
    nowcol = que[done][1]
    end[nowpos]=1
    for k in nb[nowpos]:
        if(end[k[0]]==0):
            nowcol += 1
            nowcol %= mx
            que.append([k[0],nowcol])
            ans[k[1]] = nowcol+1
    done+=1
print(mx)
for i in range(n-1): print(ans[i])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
que = deque([root])
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while que:
    x = que.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        que.append(y)
print(max([len(i) for i in graph]))
color = [0 for i in range(n+1)]
cnt = [0 for i in range(n+1)]
ng = [0 for i in range(n+1)]
for x in order:
    if x == 1:
        continue
    px = parent[x]
    color[x] = cnt[px]+1
    if color[x] == ng[px]:
        color[x] += 1
    cnt[px] = color[x]
    ng[x] = color[x]
for a,b in ab:
    if parent[a] == b:
        p = b
        c = a
    else:
        p = a
        c = b
    print(color[c])

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

C = [0] * (N-1)
stack=[0]
parent_e=[0]*N
max_c=0
while stack:
    n=stack.pop()
    c=1
    for to,i in E[n]:
        if n!=0 and parent_e[n]==i:
            continue
        c+=1 if n!=0 and C[parent_e[n]]==c else 0
        C[i]=c
        max_c=max(max_c,c)
        c+=1
        stack.append(to)
        parent_e[to]=i

print(max_c)
print('\n'.join(map(str,C)))

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

C = [0] * (N-1)
stack=[0]
max_c=0
while stack:
    n=stack.pop()
    u=set()
    for to,i in E[n]:
        if C[i]!=0:
            u.add(C[i])
    c=1
    for to,i in E[n]:
        if C[i]!=0:
            continue
        while c in u:
            c+=1
        C[i]=c
        max_c=max(max_c,c)
        c+=1
        stack.append(to)

print(max_c)
print('\n'.join(map(str,C)))

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

    
    T[a].append([b, i])
    T[b].append([a, i])


stack = [[0, 0]]  
visited = [0] * N
colors = [0] * (N - 1)
while stack:
    n, parent_color = stack.pop()
    visited[n] = 1
    color = 1

    for to, i in T[n]:
        if visited[to]:
            continue

        if color == parent_color:
            color += 1

        colors[i] = color
        stack.append([to, color])

        color += 1


print(len(set(colors)))
print(*colors, sep='\n')