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 heapq as h

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

flag=[0 for i in range(0,N+1)]
ans=[0 for i in range(0,N)]

count=0
subcount=0
q=[]
h.heapify(q)
h.heappush(q,1)
sub=[]
h.heapify(sub)
while q!=[]:
    if q==[1]:
        subcount=0
        usedcolor=0
        x=h.heappop(q)
        for p in hen[x]:
            if flag[p[0]]==0:
                subcount+=1
                h.heappush(sub,p[0])
            else:
                colored=p[0]
                usedcolor=ans[p[1]]
        count=subcount
        color=1
        for p in hen[x]:
            if flag[p[0]]==0:
                if color!=usedcolor:
                    ans[p[1]]=color
                    color+=1
                else:
                    color+=1
                    ans[p[1]]=color
                    color+=1
        flag[x]=1
        q=sub
        sub=[]
        h.heapify(sub)

    else:
        while q!=[]:
            subcount=0
            colored=0
            usedcolor=0
            x=h.heappop(q)
            for p in hen[x]:
                if flag[p[0]]==0:
                    subcount+=1
                    h.heappush(sub,p[0])
                else:
                    colored=p[0]
                    usedcolor=ans[p[1]]
            if subcount>=count:
                count=subcount+1
            color=1
            for p in hen[x]:
                if flag[p[0]]==0:
                    if color!=usedcolor:
                        ans[p[1]]=color
                        color+=1
                    else:
                        color+=1
                        ans[p[1]]=color
                        color+=1
            flag[x]=1
            if q==[]:
                q=sub
                sub=[]
                h.heapify(sub)
                break
print(count)
for i in range(1,N):
    print(ans[i])

Solution (Python):
n = int(input())
ab=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    ab.append(tmp)
link = [[] for _ in range(n)]
for tmp in ab:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

cnt=0
for l in link:
    if cnt < len(l):
        cnt=len(l)
print(cnt)

from collections import deque
from collections import defaultdict
Q = deque()
Q.append([0,0]) 
cs = defaultdict(lambda: -1)
while Q:
    now,now_color= Q.popleft()

    nxt_c=now_color
    for nxt in link[now]:
        if cs[str(now)+"_"+str(nxt)] !=-1:
            continue

        nxt_c = (nxt_c+1) % cnt
        cs[str(now)+"_"+str(nxt)] = nxt_c
        cs[str(nxt)+"_"+str(now)] = nxt_c
        Q.append([nxt,nxt_c])

for tmp in ab:
    print(cs[str(tmp[0]-1) + "_" + str(tmp[1]-1)]+1)

Solution (Python):
from collections import deque
n = int(input())
l = [0 for i in range(n)]
l2 = []
l3 = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l2.append([a,b])
    l3[a].append(b)
    l3[b].append(a)
    l[a-1] += 1
    l[b-1] += 1
a = max(l)
print(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([1,0])
rl[1] = 1
dic = {}
while len(d):
    now,c = d.popleft()
    rl[now] = 1
    if c == 0:
        count = 1
        for i in l3[now]:
            dic["{0},{1}".format(now,i)] = count
            d.append([i,count])
            count += 1
    else:
        count = 1
        for i in l3[now]:
            if rl[i] == 0:
                if c == count:
                    count += 1
                dic["{0},{1}".format(now,i)] = count
                d.append([i,count])
                count += 1
for i in range(n-1):
    print(dic["{0},{1}".format(l2[i][0],l2[i][1])])

Solution (Python):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
 
E = [[] for _ in [0]*N]
for i,ab in enumerate(AB):
    a,b = ab
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
 
done = [False]*N
done[0] = True
ans = [0]*(N-1)
q = [(0,0)]
while q:
    i,c0 = q.pop()
    c = 1
    for j,ei in E[i]:
        if done[j]:continue
        done[j] = True
        if c==c0: c+=1
        q.append((j,c))
        ans[ei] = c
        c += 1
 
print(max(ans))
for out in ans:
    print(out)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [0 for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        K = set()
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            k = len(G[u])
            c = (G_c[u] % k) + 1
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    colors[u, v] = c
                    colors[v, u] = c
                    G_c[u] = c
                    G_c[v] = c
                    K.add(c)
                    c = c % k + 1
            G_color[u] = 'BLACK'
        return K
    K = bfs(0)
    print(len(K))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

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

k = 0
for e in E:
    k = max(k, len(e))

ans = [0]*(N-1)
from collections import deque
q = deque()
q.append((0, 0))
used = [0]*N
used[0] = 1
while q:
    temp = q.pop()
    v = temp[0]
    num = temp[1]
    for t in E[v]:
        if used[t] == 1:
            continue
        used[t] = 1
        a = min(v, t)
        b = max(v, t)
        num += 1
        ans[dic[(a, b)]] = (num%k) + 1
        q.append((t, (num%k)))
print(k)
for a in ans:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

visited = [0]*N
ans = [None]*(N-1)

def dfs(v,c=-1):
    nc = 1
    for to,i in es[v]:
        if visited[to]: continue
        visited[v] = 1
        if nc==c:
            nc += 1
        ans[i] = nc
        dfs(to,nc)
        nc += 1
dfs(0)
print(max(ans))
print(*ans,sep='\n')

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for i in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, i))
  e[v].append((u, i))
res = [0] * (N - 1)
def dfs(x):
  global res
  c = 1
  vis = set()
  for y, i in e[x]: vis.add(res[i])
  
  for y, i in e[x]:
    if res[i] > 0: continue
    while c in vis: c += 1
    
    res[i] = c
    vis.add(c)
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)

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

N = int(input())
G = [list() for _ in range(N)]
E = list()
D = dict()

for _ in range(N-1):
  a,b = map(int, input().split())
  a -= 1; b -= 1;
  G[a].append(b)
  G[b].append(a)
  if a > b:
    a,b=b,a
  E.append((a,b))

k = max(len(G[i]) for i in range(N))

q = [(0,-1,-1)]
while q:
  cc = 1
  v,p,c = q.pop()
  for x in G[v]:
    if x == p:
      continue
    if cc == c:
      cc += 1
    if v<x:
      D[(v,x)] = cc
    else:
      D[(x,v)] = cc
    q.append((x,v,cc))
    cc += 1

print(k)
for i in E:
  print(D[i])

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

n = int(input())
edge = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))
colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))
print(colors)
work_q = deque()
work_q.append((1, -1, -1))
color = [-1] * (n - 1)

while work_q:
    here, prev, col = work_q.popleft()
    cnt = 1
    for to, ind in edge[here]:
        if to == prev:
            continue
        if cnt == col:
            cnt += 1
        color[ind] = cnt
        work_q.append((to, here, cnt))
        cnt += 1
print(*color, sep="\n")

Solution (Python):
import collections

n=int(input())
edges=[list(map(int,input().split())) for _ in range(n-1)]
g=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=edges[i]
  g[a].append(b)
  g[b].append(a)
k=0
pos=0
for i in range(n+1):
  if len(g[i])>k:
    k=len(g[i])
    pos=i
print(k)
dic={}
q=collections.deque()
q.append((pos,0))
checked=[0]*(n+1)
checked[pos]=1
while 1:
  if len(q)==0:
    break
  u,c=q.popleft()
  l=len(g[u])
  tcs=[i+1 for i in range(l)]
  if c in tcs:
    tcs.remove(c)
  pos=0
  for i in range(len(g[u])):
    v=g[u][i]
    if checked[v]==0:
      checked[v]=1
      q.append((v,tcs[pos]))
      dic[(u,v)]=tcs[pos]
      dic[(v,u)]=tcs[pos]
      pos+=1
for i in range(n-1):
  a,b=edges[i]
  print(dic[(a,b)])

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


def dfs(v, c):
    nc = 0
    k = 0
    for nv, idx in edge[v]:
        if status[nv] == 0:
            nc = nc + 1 + ((nc + 1) == c)
            color[idx] = nc
            status[nv] = 1
            k = max(k, dfs(nv, nc))
    return max(nc, k)


N = int(input())
edge = [[] for _ in range(N)]
for idx, line in enumerate(sys.stdin.readlines()):
    a, b = map(lambda x: int(x) - 1, line.split())
    edge[a].append((b, idx))
    edge[b].append((a, idx))

status = [0] * N
color = [0] * (N - 1)
status[0] = 1
K = dfs(0, 0)

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

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

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

def col(now,color):
  c=1
  for (b,j) in A[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):
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
sortedAB = sorted(AB)
con = {i: [] for i in range(1, N+1)}
color = [0] * (N + 1)
for a, b in sortedAB:
    con[a].append(b)

for i in range(1, N + 1):
    now_c = 1
    for c in con[i]:
        if color[i] == now_c:
            now_c += 1
        color[c] = now_c
        now_c += 1

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

a = 0

Solution (Python):
from collections import deque

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

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

nodes = deque([1])
count = [0] * (N + 1)

while nodes:
    node = nodes.popleft()
    nodes.extend(edges[node])

    c = 0
    for n in edges[node]:
        c += 1 + (c + 1 == count[node])
        count[n] = c

print(max(count))
for i in ends:
    print(count[i])

Solution (Python):
n=int(input())
node={i:[] for i in range(1,n+1)}
visited=[False for i in range(n+1)]
q=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    q.append((a,b))

mother=q[0][0]
visited[mother]=True

d=[]
e=[]


paint={i:{} for i in range(1,n+1)}

mother_paint=[0 for i in range(n+1)]


c=1
for child in node[mother]:
    visited[child]=True
    paint[mother][child]=c
    paint[child][mother]=c
    mother_paint[child]=c
    c+=1
    d.append(child)
    
while d:
    for parent in d:
        p=1 
        for child in node[parent]:
            if visited[child]==False:
                visited[child]=True
                if p!=mother_paint[parent]:
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
                else:
                    p+=1
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
    if e:
        d=e
        e=[]
    else:
        d=[]
        e=[]
K=0
for i in range(1,n+1):
    K=max(K,len(node[i]))
print(K)
for i in range(n-1):
    s,t=q[i][0],q[i][1]
    print(paint[s][t])

Solution (Python):
n=int(input())
node={i:[] for i in range(1,n+1)}
visited=[False for i in range(n+1)]
q=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    q.append((a,b))

mother=q[0][0]
visited[mother]=True

d=[]
e=[]


paint={i:{} for i in range(1,n+1)}

mother_paint=[0 for i in range(n+1)]


c=1
for child in node[mother]:
    visited[child]=True
    paint[mother][child]=c
    paint[child][mother]=c
    mother_paint[child]=c
    c+=1
    d.append(child)
    
while d:
    for parent in d:
        p=1 
        for child in node[parent]:
            if visited[child]==False:
                visited[child]=True
                if p!=mother_paint[parent]:
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
                else:
                    p+=1
                    paint[parent][child]=p
                    paint[child][parent]=p
                    mother_paint[child]=p
                    p+=1
                    e.append(child)
    if e:
        d=e.copy()
        e=[]
    else:
        d=[]
        e=[]
K=0
for i in range(1,n+1):
    K=max(K,len(node[i]))
print(K)
for i in range(n-1):
    s,t=q[i][0],q[i][1]
    print(paint[s][t])

Solution (Python):
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]

connects = [[] for i in range(n+1)]
for e in edges:
    connects[e[0]].append(e[1])
    connects[e[1]].append(e[0])

x = max([len(i) for i in connects])
print(x)

from collections import deque
nodeQ = deque([1])
begin = {1: 0}
ecolors = {}

while len(nodeQ):
    node = nodeQ.popleft()
    ncolor = begin[node]
    nconnect = list(filter(lambda n: n > node, connects[node]))
    
    for i, ni in enumerate(nconnect):        
        begin[ni] = (ncolor + i) % x + 1
        ecolors[(node, ni)] = begin[ni]
        
        nodeQ.append(ni)
             
for e in edges:
    print(ecolors[e])

Solution (Python):
N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

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

k=[0]*N

from collections import deque

q=deque([0])
visited=[0]*N
ans={}
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    visited[x]=1
    cnt=1
    for i in G[x]:
        if visited[i]!=0:continue
        if p[x]==cnt:
            cnt+=1
        ans[(x,i)]=cnt
        ans[(i,x)]=cnt

        p[i] = cnt
        cnt += 1
        kmx=max(kmx,cnt-1)
        q.append(i)

print(kmx)
for i in range(N-1):
    print(ans[(a[i],b[i])])

Solution (Python):
def main():
  import sys
  input=sys.stdin.readline
  n=int(input())
  
  edges=[]
  for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges.append([a,b,i])

  edges.sort(key=lambda i:i[0])
  color=[0]*(n-1)
  head=[0]*n 
  before=[0]*n 
  
  for i in range(n-1):
    a=edges[i][0]
    b=edges[i][1]
    index=edges[i][2]
    if before[a]+1==head[a]:
      c=before[a]+2
    else:
      c=before[a]+1
    before[a]=c
    head[b]=c
    color[index]=c
    
  print(max(color))
  print(*color,sep='\n')
  
if __name__=='__main__':
  main()

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

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)
  
def make_tree(graph, root) -> (list, list, list):
    INF = 10 ** 15
    dist = [INF] * len(graph)
    parent = [-1] * len(graph)
    stack = [root]
    dist[root] = 0
    order = []
    parent[root] = root
    while stack:
        s = stack.pop()
        order.append(s)
        for g in graph[s]:
            if dist[g] > dist[s] + 1:
                dist[g] = dist[s] + 1
                parent[g] = s
                stack.append(g)
    return dist, parent, order
    
dist, parent, order = make_tree(graph, 1)

color = [-1] * (N + 1)
for s in order:
    ng = color[s]
    c = 1
    for g in graph[s]:
        if parent[s] == g:
            continue
        if c == ng:
            c += 1
        color[g] = c
        c += 1

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

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

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

vc=[0]*n
ec=[0]*(n-1)
h=1

for v,c in enumerate(g):
  t=1
  for b,i in c:
    if vc[v]==t:
      t+=1
    vc[b]=t
    ec[i]=t
    h=max(h,t)
    t+=1

print(h)
for i in range(n-1):
  print(ec[i])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)] 
edges = [[] for _ in range(N+1)] 
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

order = [] 
parent = [0] * (N+1) 
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for y in edges[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1) 
for o in order:
    ng = color[o]
    c = 1
    for z in edges[o]:
        if z == parent[o]:
            continue
        if c == ng:
            c += 1
        color[z] = c
        c += 1

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

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

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)] 
edges = [[] for _ in range(N+1)] 
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

order = [] 
parent = [0] * (N+1) 
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for y in edges[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1) 
for o in order:
    ng = color[o]
    c = 1
    for z in edges[o]:
        if z == parent[o]:
            continue
        if c == ng:
            c += 1
        color[z] = c
        c += 1

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

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

Solution (Python):
from collections import deque
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n+1)]
color = [set([]) for _ in range(n+1)]
ans = {}
for a, b in ab:
    tree[a].append(b)

q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    cnt = 1
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            
            if cnt in color[now]:
                cnt += 1
            color[i].add(cnt)
            ans[(now, i)] = cnt
            cnt += 1

print(max(ans.values()))
for i in ab:
    print(ans[i])

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

n = int(input())
arr = []

for i in range(n-1):
    S = input()
    ar = [int(s) for s in S.split(" ")]
    arr.append(ar)

def prepare(n, arr):
    data = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    childNums = [0 for i in range(n)]

    for ar in arr:
        start = ar[0] - 1
        to = ar[1] - 1
        data[start].append(to)
        data[to].append(start)
    return data, nodeStates, childNums


data, nodeStates, childNums = prepare(n, arr)
mmk = {}
def generateID(start,to):
    if start < to:
        start,to = to, start

    return start * 100000 + to

def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    nodeStates[currentNode] = 1
    childNums[currentNode] = len(childNodes)
    kk = 0
    for ch in childNodes:
        if nodeStates[ch] == -1:
            kk = kk + 1
            if kk == x:
                kk = kk + 1
            mmk[generateID(currentNode+1,ch+1)] = kk
            dfs(ch, arr, kk)

dfs(0, data, -1)
print(max(childNums))
for ar in arr:
    start = ar[0]
    to = ar[1]
    print(mmk[generateID(start,to)])

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

N=int(input())
ab=[list(map(int, input().split())) for _ in range(N-1)]
to=[[] for _ in range(N)]
color=[0 for _ in range(N-1)]
for i in range(N-1):
    a, b=ab[i]
    a-=1
    b-=1
    to[a].append([b, i])
    to[b].append([a, i])

def dfs(v, p=-1, c=-1):
    k=1
    for i in range(len(to[v])):
        u, index=to[v][i]
        if u==p:
            continue
        if k==c:
            k+=1
        color[index]=k
        dfs(u, v, k)
        k+=1

dfs(0)
print(max(color))
for i in range(N-1):
    print(color[i])

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(100000)

n = int(input())
arr = []
for i in range(n - 1):
    arr.append([int(s) for s in input().split(" ")])

mmk = {}

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]


def generateID(fr, to):
    if to < fr:
        fr, to = to, fr
    return fr * 100000 + to


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s



def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mmk[generateID(currentNode + 1,childNodeIndex + 1)] = kk
            dfs(childNodeIndex, arr, kk)


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in arr:
    a0 = ar[0]
    a1 = ar[1]
    print(mmk[generateID(a0,a1)])

Solution (Python):
from sys import setrecursionlimit


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


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


setrecursionlimit(100000)

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

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

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

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

Solution (Python):
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

from collections import deque

n = ni()
ab = nan(n - 1)

to = [[] for i in range(n)]
for i in range(n - 1):
    a, b = ab[i][0] - 1, ab[i][1] - 1
    to[a].append(b)
    to[b].append(a)

q = deque()
q.append((0, 0, -1))
color = 0
d = dict()
m = 0
while len(q):
    p = q.pop()
    j = 0
    for i in to[p[0]]:
        if i == p[2]:
            continue
        j += 1
        if j == p[1]:
            j += 1
        m = max(m, j)
        q.append((i, j, p[0]))
        d[(p[0], i)] = j

print(m)
for i in range(n - 1):
    print(d[(ab[i][0] - 1, ab[i][1] - 1)])

Solution (Python):



import numpy
from collections import defaultdict, deque

def bfs(tree, k):
  dq = deque()
  dq.append((-1, 1, 0))
  print(k)
  ans = dict()
  while dq:
    _, s, c = dq.popleft()
    if _ != -1:
      ans[(_, s)] = c
    for i, t in enumerate(tree[s]):
      dq.append((s, t, ((c+i) % (k)+1)))
  return ans

def main():
  n = int(input())
  edges = [tuple(map(int, input().strip().split())) for _ in range(n-1)]
  counts = numpy.zeros(n)
  tree = defaultdict(list)
  for s, t in edges:
    counts[s-1] += 1
    counts[t-1] += 1
    tree[s].append(t)
  k = int(numpy.max(counts))
  ans = bfs(tree, k)
  for edge in edges:
    print(ans[edge])

if __name__=='__main__':
  main()

Solution (Python):

N = int(input())
EDGES = [[] for _ in range(N+1)]
P = [(set(), 1) 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 = [None for i in range(N-1)]

def dfs(root):
  
  stack = [(root, -1, -1)]
  visited = set()

  while stack:
    u, parent, color = stack.pop()
    visited.add(u)

    nextColor = 1

    for (v, index) in EDGES[u]:
      if v not in visited and v != parent:
        if nextColor == color:
          nextColor += 1
        stack.append((v, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

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

Solution (Python):
from collections import deque

def solve(n, AB):
    g = [[] for _ in range(n + 1)]
    for i, (a, b) in enumerate(AB):
        g[a].append(b)

    q = deque(maxlen=n)
    q.append((1, -1))
    k = 0
    color = {}
    while q:
        node, col = q.popleft()
        count = 0
        for i in range(len(g[node])):
            if i == col:
                count += 1
            color[(node, g[node][i])] = count
            q.append((g[node][i], count))
            count += 1
        if k < count - 1:
            k = count - 1
    return [k + 1] + [color[(a, b)] + 1 for a, b in AB]

_n = int(input())
_AB = [tuple(map(int, input().split())) for _ in range(_n - 1)]
print(*solve(_n, _AB), sep='\n')

Solution (Python):
n = int(input())
raw = []
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw.append([a,b])
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
clr = [10**6 for _ in range(n)]
clr2 = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
rank[0] = 0
clr[0] = 0
clr2[0] = 0
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        clr[y] = clr2[x] + 1
        clr2[y] = clr[y]
        clr2[x] += 1
        rank[y] = rank[x] + 1
        now.append(y)
maxi = 0
for i in range(n):
  maxi = max(maxi,len(peer[i]))
print(maxi)
for i in range(n-1):
  a,b = raw[i]
  if rank[a] < rank[b]:
    c = b
  else:
    c = a
  print(clr[c] % maxi + 1)

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, pc=-1, p=-1):
    c = 1
    for u, idx in E[v]:
        if (u == p):
            continue
        if (c == pc): 
            c += 1
        Ans[idx] = c
        dfs(u, c, v)
        c += 1

dfs(1)
print("\n".join(map(str, Ans)))

Solution (Python):
from math import ceil

def main():
    N = int(input())
    AB = [list(map(int,input().split())) for _ in range(N-1)]

    Edge = [[] for _ in range(N + 1)]

    for i in range(N-1):
        a,b = AB[i]
        Edge[a].append((b,i))
        Edge[b].append((a,i))
    Ans = [-1]*N

    stack = [1]
    gone = [False]*(N + 1)
    gone[1] = True
    ans = 0
    Index = {1:0}
    while len(stack) > 0:
        color = 1
        start = stack.pop(-1)
        parent = Index[start]
        for e,index in Edge[start]:
            if not(gone[e]):
                Index[e] = start
                stack.append(e)
                gone[e] = True
                if parent == color:
                    color += 1
                    Ans[index] = color
                    Index[e] = color
                else:
                    Ans[index] = color
                    Index[e] = color
                color += 1
        ans = max(ans,color-1)
    print(ans)
    print(*Ans[:-1],sep="\n")
    return

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())

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


ans = [0]*(n-1)

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

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