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 os
import sys
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
sys.setrecursionlimit(1000000)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p, prev):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		if now == prev:
			now = (now+1)%mx
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u, col[edges[i, u]])

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0,-1)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Solution (Python):
import os
import sys
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
sys.setrecursionlimit(1000000)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p, prev):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		if now == prev:
			now = (now+1)%mx
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u, col[edges[i, u]])

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0,-1)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
g = [[] for _ in range(n)] 
ab = []
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    ab.append((a,b))
    g[a].append(b)
    g[b].append(a)

root = 0
parent = [0]*n
deq = deque([root])
order = [root]

color = [-1]*n
deq = deque([root])
while deq:
    fr = deq.pop()
    ng = color[fr]
    c = 0
    for go in g[fr]:
        if go == parent[fr]:
            continue
        if c == ng:
            c += 1
        parent[go] = fr
        color[go] = c
        c += 1
        deq.append(go)
        order.append(go)
rank = [0]*n
for i,j in enumerate(order):
    rank[j] = i
print(max(color)+1)
for a,b in ab:
    if rank[a] < rank[b]:
        print(color[b]+1)
    else:
        print(color[a]+1)

Solution (Python):

from collections import deque

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

tree = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(X):
    tree[a].append((b, i))
    tree[b].append((a, i))

color = [0] * (N - 1)
nodes = [set() for _ in range(N + 1)]
visited = [False] * (N + 1)

q = deque([1])
visited[1] = True
while q:
    u = q.popleft()
    c = 1
    for v, i in tree[u]:
        if visited[v]:
            continue

        while c in nodes[v] or c in nodes[u]:
            c += 1
        color[i] = c
        nodes[u].add(c)
        nodes[v].add(c)
        visited[v] = True
        q.append(v)

print(max(len(v) for v in tree))
print(*color, sep="\n")

Solution (Python):
from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

M=max(F)

C=[0]*(N-1)
G=[set() for _ in range(N+1)]
A=[-1]*(N+1)

T={i:False for i in range(1,N+1)}
T[1]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    y=1
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)
            
            p,q=min(v,w),max(v,w)

            c=(A[v]+y)%M
            
            A[w]=c
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)
            y+=1

print(max(C)+1)
print("\n".join(map(lambda x:str(x+1),C)))

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

next_set = deque([(0,0)])
colors = [0]*(N-1)
while next_set:
    p, i = next_set.popleft()
    cnt = 1 if colors[i] != 1 else 2
    for q, j in edges[p]:
        if colors[j] != 0:
            continue
        colors[j] = cnt
        cnt += 1
        if cnt == colors[i]:
            cnt += 1
        next_set.append((q, j))
print(max(colors))
print(*colors, sep="\n")

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()


graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)

check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print(ans[key])

Solution (Python):
import sys
from collections import defaultdict, deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

g = [[] for _ in range(N)]
deg = [0] * N
ab = defaultdict(int)

for _ in range(N - 1):
    a, b = map(int1, readline().split())
    g[a].append(b)
    g[b].append(a)
    deg[a] += 1
    deg[b] += 1
    ab[(a, b)] = -1

color = [-1] * N

print(max(deg))

C = [0] * N
C[0] = -1

que = deque([0])

while len(que) != 0:
    idx = que.popleft()
    tmp = 1
    for i in g[idx]:
        if C[i] != 0:
            continue
        a, b = idx, i
        if tmp == C[idx]:
            tmp += 1
        ab[(a, b)] = tmp
        C[i] = tmp
        que.append(i)
        tmp += 1

for v in ab.values():
    print(v)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    n = int(input())
    edge = [[] for i in range(n)]
    side = []
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
        side.append([a,b])
    I = collections.defaultdict(lambda : 0)
    k = 0
    for i in edge:
        k = max(k,len(i))
    print(k)
    color = [INF]*(n)
    d = [INF]*(n)
    d[0] = 0
    q = collections.deque([0])
    while q:
        p = q.popleft()
        color_num = 1
        for v in edge[p]:
            if d[v] == INF:
                q.append(v)
                d[v] = d[p] + 1
                if color_num == color[p]:
                    color_num+=1
                color[v] = color_num
                I[(p,v)] = color_num
                I[(v,p)] = color_num
                color_num+=1
    for i,j in side:
        print(I[(i,j)])

Solution (Python):
from collections import deque
N = int(input())
E = [[] for _ in range(N)]
  
for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  
  E[a].append([i,b])
  E[b].append([i,a])
  
k = 0
for e in E:
  k = max(k, len(e))
print(k)


def bfs():
  colors = [-1 for _ in range(N-1)]
  visited = [False for _ in range(N)]
  d = deque()
  d.append([0,-1])
  while d:
    now,edge_color = d.pop()
    visited[now] = True
    cand_color = 1
    for i, nxt in E[now]:
      
      if visited[nxt]:
        continue 
      if colors[i] > -1:
        assert("１エッジに２色塗ろうとする・・・？")
        continue
      if cand_color == edge_color:
        cand_color += 1
      colors[i] = cand_color
      d.append([nxt, colors[i]])
      cand_color += 1
  return colors

colors = bfs()

for i in range(len(colors)):
  print(colors[i])

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

def abc146_d():
    n = int(input())
    Q = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]

    deg = [0] * n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1: nouse = color[(min(s, p), max(s, p))]
        c = 1
        for t in adj[s]:
            if t == p: continue
            if c == nouse: c += 1
            color[(min(s, t), max(s, t))] = c
            dfs(t, s)
            c += 1

    dfs(1, -1)

    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

if __name__ == '__main__':
    abc146_d()

Solution (Python):
import queue
n=int(input())
cf=[0]*n
cg=[0]*(n-1)
ce=[[] for _ in range(n)]
e=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
  ce[a-1]+=[i]
  ce[b-1]+=[i]
k=len(max(e,key=len))
q=queue.Queue()
q.put(0)
while not q.empty():
  now=q.get()
  cf[now]=1
  c=0
  for i in ce[now]:
    if cg[i]:c=cg[i]
  j=1
  for i in ce[now]:
    if j==c:j+=1
    if cg[i]:continue
    cg[i]=j
    j+=1
  for i in e[now]:  
    if cf[i]:continue
    q.put(i)
print(k)
for i in cg:
  print(i)

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

col=[0 for i in range(n-1)]
fl=[0 for i in range(n)]
s=[[0,0]]
mc=0
while len(s):
  ns=[]
  for i in s:
    fl[i[0]]=1
    cc=1
    for j in e[i[0]]:
      if not(fl[j[0]]):
        if cc==i[1]:
          cc+=1
        col[j[1]]=cc
        mc=max(mc,cc)
        ns.append([j[0],cc])
        cc+=1
  s=ns

print(mc)
for i in col:
  print(i)

Solution (Python):
f=lambda:map(int,input().split())
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
u=[0]*n
q=[(0,0)]
while q:
  v,s=q.pop()
  u[v]=1
  t=1
  for c,i in g[v]:
    if u[c]: continue
    if t==s: t+=1
    l[i]=t
    q+=[(c,t)]
    t+=1
print(max(l))
for i in l: print(i)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
def dfs(v,p=-1,s=-1):
  t=1
  for c,i in g[v]:
    if c==p: continue
    if t==s: t+=1
    l[i]=t
    dfs(c,v,t)
    t+=1
dfs(0)
print(max(l))
for i in l: print(i)

Solution (Python):
from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col = [0]*(n-1)
visited = [0]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(not visited[next_v[1]]):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            c+=1
            visited[next_v[1]] = 1
            que.append(next_v)
print(max(col))
for i in col:
    print(i)

Solution (Python):
from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col = [0]*(n-1)
visited = [0]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(not visited[next_v[1]]):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            c+=1
            visited[next_v[1]] = 1
            que.append(next_v)
print(max(col))
for i in col:
    print(i)

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

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

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

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])

Solution (Python):
def resolve():
    N = int(input())
    g = {}
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append((b-1, i))
        g.setdefault(b-1, [])
        g[b-1].append((a-1, i))
        
    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        color = 1 if prevcol != 1 else 2
        for nxt, colidx in g[node]:
            if colors[colidx] is None:
                colors[colidx] = color
                nodes.append((color, nxt))
                color += 1 if prevcol != color+1 else 2

    print(maxdeg)
    for col in colors:
        print(col)
            



if '__main__' == __name__:
    resolve()

Solution (Python):
def resolve():
    N = int(input())
    g = {}
    edges_to_idx = {}
    edges = []
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges_to_idx.setdefault("{}-{}".format(a-1, b-1), i)
        edges_to_idx.setdefault("{}-{}".format(b-1, a-1), i)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx]
            coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            if colors[coloridx] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
                coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            colors[coloridx] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for col in colors:
        print(col)
            
            




if '__main__' == __name__:
    resolve()

Solution (Python):
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
                maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Solution (Python):
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Solution (Python):
from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        
    return n,nList,edges

def bfs(s,nList):
    
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)

Solution (Python):
import sys
from collections import deque

n = int(sys.stdin.readline())
G = [[] for _ in range(n+1)]
G_order = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G_order.append(b)

que = deque([0])
C = [0]*(n+1)
while que:
    nw = que.popleft()
    c = 1
    for nx in G[nw]:
        if c==C[nw]:
            c+=1
        C[nx] = c
        c += 1
        que.append(nx)

print(max(C))
for i in G_order:
    print(C[i])

Solution (Python):
import sys
from collections import deque

n = int(sys.stdin.readline())
G = [[] for _ in range(n+1)]
G_order = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G_order.append(b)

que = deque([0])
C = [0]*(n+1)
while que:
    nw = que.popleft()
    c = 1
    for nx in G[nw]:
        if c==C[nw]:
            c+=1
        C[nx] = c
        c += 1
        que.append(nx)

print(max(C))
for i in G_order:
    print(C[i])

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

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

root = 1
parent = [0] * (n+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        
color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue 
        if c == ng:
            c += 1
        color[y] = c
        c += 1

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

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

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

root = 1
parent = [0] * (n+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        
color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue 
        if c == ng:
            c += 1
        color[y] = c
        c += 1

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

Solution (Python):
from collections import defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

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

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

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

Solution (Python):
from collections import defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

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

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

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

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

from collections import deque
q=deque([1])
color=[0]*(n+1)
while q:
  cur=q.popleft()
  c=1
  for nx in G[cur]:
    if c==color[cur]:
      c+=1
    color[nx]=c
    c+=1
    q.append(nx)

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

Solution (Python):
from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

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

Solution (Python):
from collections import deque, defaultdict
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
d = [0] * (N + 1)
G = [[] for _ in range(N + 1)]
for a, b in ab:
    d[a] += 1
    d[b] += 1
    G[a].append(b)
    G[b].append(a)
print(max(d))

color = defaultdict(int)
q = deque([[1, 0]])
seen = [0] * (N + 1)
while q:
    v, c = q.popleft()
    seen[v] = 1
    tem = 1
    for u in G[v]:
        if seen[u]:
            continue
        if tem == c:
            tem += 1
        q.append([u, tem])
        i, j = min(v, u), max(v, u)
        color[(i, j)] = tem
        tem += 1

for a, b in ab:
    i, j = min(a, b), max(a, b)
    print(color[(i, j)])

Solution (Python):
from queue import Queue

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = {}
        
    def add_edge(self, v1, v2):
        self.adjacency_dict[v1][v2] = -1
        self.adjacency_dict[v2][v1] = -1
    
    def paint(self, v1, v2, color):
        self.adjacency_dict[v1][v2] = color
        self.adjacency_dict[v2][v1] = color
        
    def get_color(self, v1, v2):
        return self.adjacency_dict[v1][v2]
    
    def next_vertices(self, v):
        return self.adjacency_dict[v]


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


tree = Graph()
for i in range(1, N+1):
    tree.add_vertex(i)
for a,b in edges:
    tree.add_edge(a, b)

most_edges_vertex = -1
max_colors = 0
for k,v in tree.adjacency_dict.items():
    if len(v) > max_colors:
        most_edges_vertex = k
        max_colors = len(v)



q = Queue()
q.put([most_edges_vertex, -1])  
while not q.empty():
    vertex, prev_color = q.get()
    nexts = tree.next_vertices(vertex)
    color = 1 if prev_color != 1 else 2

    for v,c in nexts.items():
        if c > 0:
            continue
        q.put([v, color])
        
        
        tree.paint(vertex, v, color)
        
        
        color += 1
        if color == prev_color:
            color += 1

print(max_colors)
for v1,v2 in edges:
    print(tree.get_color(v1, v2))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uvs = [None]*(n-1)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    uvs[i] = (u,v)

s = [(0, -1)]
cs = {(0,-1): -1}
seen = [False]*n
seen[0] = True
while s:
    u,prev = s.pop()
    val = 0
    cc = cs[u,prev]
    for v in ns[u]:
        if seen[v]:
            continue
        if val==cc:
            val += 1
        cs[v,u] = val
        val += 1
        seen[v] = True
        s.append((v,u))
ans = []
for u,v in uvs:
    if (u,v) in cs:
        ans.append(cs[u,v]+1)
    else:
        ans.append(cs[v,u]+1)
print(max(ans))
write("\n".join(map(str, ans)))

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


def main():
  N = int(input())
  G = [[] for _ in range(N)]
  dic = {}
  for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    dic[(a, b)] = i
    dic[(b, a)] = i

  color = [0]*(N-1)
  upcol = [0]*(N)
  upcol[0] = None
  visited = set()
  q = deque([0])
  max_col = 0

  while len(q):

    now = q.popleft()
    visited.add(now)
    c = 0

    for next_ in G[now]:
      if next_ in visited:
        continue
      c += 1
      if upcol[now] == c:
        c += 1

      color[dic[(now, next_)]] = c
      upcol[next_] = c

      q.append(next_)

    max_col = max(max_col, c)

  print(max_col)
  print(*color, sep='\n')


if(__name__ == '__main__'):
  main()

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  G = [[] for _ in range(N)]
  dic = {}
  for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    dic[(a, b)] = i
    dic[(b, a)] = i

  color = [0]*(N-1)
  upcol = [0]*(N)
  upcol[0] = None
  visited = set()
  q = deque([0])
  max_col = 0

  while len(q):

    now = q.popleft()
    visited.add(now)
    c = 0

    for next_ in G[now]:
      if next_ not in visited:
        c += 1
        if upcol[now] is None or not(upcol[now] == c):
          color[dic[(now, next_)]] = c
          upcol[next_] = c
        else:
          c += 1
          color[dic[(now, next_)]] = c
          upcol[next_] = c
        q.append(next_)

    max_col = max(max_col, c)

  print(max_col)
  print(*color, sep='\n')


if(__name__ == '__main__'):
  main()