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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append((b, i))
    graph[b].append((a, i))
color = [-1] * (n + 1)
color[1] = -2
ans = [0] * (n - 1)

def bfs(s):
    stack = deque([s])
    while stack:
        num = 1
        now = stack.pop()
        for next, idx in graph[now]:
            if color[next] != -1:
                continue
            if color[now] == num:
                num += 1
            color[next] = num
            ans[idx] = num
            num += 1
            stack.append(next)


bfs(1)
print(max(ans))
print('\n'.join(map(str, ans)))

Solution (Python):



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


ans = [0] * (N-1)
used = [False] * (N-1)
q = []
q.append((0, 0)) 

while q:
    curr, pc = q.pop()
    nxt_es_color = 1
    for nxt, es_num in es[curr]:
        if used[es_num]:
            continue
        if nxt_es_color == pc:
            nxt_es_color += 1

        ans[es_num] = nxt_es_color
        used[es_num] = True
        q.append((nxt, ans[es_num]))
        nxt_es_color += 1


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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys


mod = 10 ** 9 + 7

from collections import deque



N = getN()
dist = [[] for i in range(N + 1)]

edge = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a].append(b)
    dist[b].append(a)
    
    edge[(a, b)] = i
    edge[(b, a)] = i

ignore = [-1] * (N + 1)
ignore[1] = 0

ans = [0] * (N - 1)

pos = deque([1])
while len(pos) > 0:
    u = pos.popleft()
    
    j = 1
    for i in dist[u]:
        if ignore[i] < 0:
            
            if j == ignore[u]:
                j += 1
            
            ignore[i] = j
            
            ans[edge[(i, u)]] = j
            pos.append(i)
            j += 1
print(max(ans))
for a in ans:
    print(a)

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

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

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)


while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        


color = [-1] * (N+1)
for x in seen:
    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

ans = []
for a,b in ab:
    ans.append(color[b])

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

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
inv = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append((b - 1, i))
    inv[a - 1] += 1
    g[b - 1].append((a - 1, i))
    inv[b - 1] += 1
k = max(inv)
print(k)
s = [0]
d = [-1] * n
d[0] = [-2]
ans = [0] * (n - 1)
while s:
    p = s.pop()
    c = 1
    for node, idx in g[p]:
        if d[node] == -1:
            if c == d[p]:
                c += 1
            d[node] = c
            ans[idx] = c
            c += 1
            s.append(node)
for x in ans:
    print(x)

Solution (Python):
from collections import deque
n=int(input())
edge=[[] for i in range(n+1)]
ab=[]
ans=dict()
for i in range(n-1):
  a,b=map(int,input().split())
  ab.append([a,b])
  ans[(a,b)]=0
  edge[a].append(b)
  edge[b].append(a)
hantei=0  
for i in edge:
  if hantei<len(i):
    hantei=len(i)
iro=hantei
print(iro)
color_list=[0]*(n+1)
def bfs(x,ans):
  qu=deque([])
  qu.append(1)
  count=1
  while qu:
    now=qu.popleft()
    if now!=1:
      pre=qu.popleft()
    else:
      pre=0
    count=1
    for i in edge[now]:
      if i!=pre:
        qu.append(i)
        qu.append(now)
        if now!=1 and ans[(pre,now)]==count:
          count+=1
        ans[(now,i)]=count
        count+=1
  return ans
bfs(1,ans)
for i,j in ab:
  print(ans[(i,j)])

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

n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)

edge=[[] for i in range(n)]
k=0

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

color_dict={}

def dfs(x, last=-1, ban_color=-1):
    global k
    color=1
    for to in edge[x]:
        if to==last:
            continue
        if color==ban_color:
            color+=1
        color_dict[(x,to)]=color
        k=max(k,color)
        dfs(to,x,color)
        color+=1
dfs(0)
print(k)

for i in range(n-1):
    if (a[i],b[i]) in color_dict:
        print(color_dict[(a[i],b[i])])
    else:
        print(color_dict[(b[i],a[i])])

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  from collections import deque
  from collections import defaultdict
  n=int(input())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  g=[[] for _ in range(n)]
  for i,abi in enumerate(ab):
    a,b=abi
    g[b-1].append(a-1)
    g[a-1].append(b-1)
  todo=deque([(0,-1)])
  dc={}
  while len(todo)>0:
    a,pc=todo.popleft()
    l=g[a]
    c=0
    for li in l:
      d,e=min(a,li),max(a,li)
      if (d,e) not in dc:
        c+=1 if c+1!=pc else 2
        dc[(d,e)]=c
        todo.append([li,c])
  print(max(dc.values()))
  for a,b in ab:
    print(dc[(a-1,b-1)])
if __name__=='__main__':
  main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  g=[[] for _ in range(n)]
  for i,abi in enumerate(ab):
    a,b=abi
    g[b-1].append([a-1,i])
    g[a-1].append([b-1,i])
  seen=[-1]*(n-1)
  todo=[[0,-1]]
  while len(todo)>0:
    a,ca=todo.pop()
    l=g[a]
    c=0
    for li in l:
      if seen[li[1]]==-1:
        c+=1 if c+1!=ca else 2
        seen[li[1]]=c
        todo.append([li[0],c])
  print(max(seen))
  for s in seen:
    print(s)
if __name__=='__main__':
  main()

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

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

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)

while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        


color = [-1] * (N+1)
for x in seen:
    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

ans = []
for a,b in ab:
    ans.append(color[b])

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque, defaultdict

sys.setrecursionlimit(10**7)
N = int(input())
edges = [[] for _ in range(N)]
nodeinput = defaultdict(int) 
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    if a > b:
        a, b = b, a
    nodeinput[(a-1, b-1)] = i

seen = [0]*N
output = [0]*(N-1) 

stack = deque()
stack.append([(0, -1)]) 
maxcolor = 0
while stack[0]:
    nstack = []
    cstack = stack.pop()
    
    for val in cstack:
        ni, pc = val
        seen[ni] = 1
        color = 1
        if color == pc:
            color += 1
        for edgei in edges[ni]:
            if seen[edgei] == 0:
                nstack.append((edgei, color))
                if ni > edgei: 
                    ni, edgei = edgei, ni
                output[nodeinput[(ni, edgei)]
                ] = color
                if maxcolor < color:
                    maxcolor = color
                color += 1
                if color == pc:
                    color += 1
    stack.append(nstack)

print(maxcolor)
for out in output:
    print(out)

Solution (Python):
from collections import deque

def bfs(s):
    q = deque()
    q.append([s, 0])
    while q:
        x, y = q.popleft()
        for g in G[x]:
            if color[g[1]] == -1:
                color[g[1]] = y + 1
                y += 1
                y %= k
                q.append([g[0], y])
    return

n = int(input())
G = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, i])
    G[b].append([a, i])
k = 0
for g in G:
    k = max(k, len(g))
color = [-1] * (n - 1)
bfs(0)
print(k)
for i in color:
    print(i)

Solution (Python):
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])
from collections import deque
d = deque([(0,-1)])
ans = [0 for i in range(n-1)]
while d:
    a,noc = d.popleft()
    c = 1 if noc != 1 else 2
    for b,i in g[a]:
        if ans[i] == 0:
            ans[i] = c
            d.append((b,c))
        else:
            continue
        c += 1 if c+1 != noc else 2
print(max(ans))
for i in range(n-1):
    print(ans[i])

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

n=int(input())


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

ans = [0]*(n-1)

def dfs(target,parent_color,parent):
    next_color = 1

    for a,b in g[target]:
        if target == parent:
            continue
        if next_color == parent_color:
            next_color += 1
        if ans[b] != 0:
            continue
        
        ans[b] = next_color
        next_color += 1
        dfs(a,ans[b],target)
    
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append((b,i))
    g[b].append((a,i))


dfs(0,-1,-1)

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

Solution (Python):
from collections import deque
def main():
    
    n = int(input())
    nodes_edges_data = {e: [] for e in range(1, n + 1)}
    edges_data_to_number = {}
    for i1 in range(n - 1):
        a, b = tuple(map(int, input().split()))
        nodes_edges_data[a].append(b)
        nodes_edges_data[b].append(a)
        edges_data_to_number[(a, b)] = i1
        edges_data_to_number[(b, a)] = i1
    
    edges_color = [-1] * (n - 1)
    nodes_num = [0] * (n + 1)
    nodes_num[1] = -1
    max_edges_per_node = 0
    nodes_next = deque([1])
    nodes_next_next = deque()
    nodes_seen = set()
    while len(nodes_seen) < n:
        while nodes_next:
            e = nodes_next.pop()
            nodes_seen.add(e)
            adj_nodes = nodes_edges_data[e]
            nodes_next_next += adj_nodes
            num_of_nodes = len(adj_nodes)
            max_edges_per_node = max(max_edges_per_node, num_of_nodes)
            num = nodes_num[e]

            for adj_node in adj_nodes:
                if not adj_node in nodes_seen:

                    num = (num + 1) % max_edges_per_node
                    edges_color[edges_data_to_number[(e, adj_node)]] = num
                    
                    nodes_num[adj_node] = num
        nodes_next_next_set = set(nodes_next_next)
        nodes_next += deque(nodes_next_next_set - nodes_seen)
        nodes_next_next = deque()

    
    print(max(edges_color) + 1)
    for i in range(n - 1):
        print(edges_color[i] + 1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    root = [[] for _ in range(N)]
    node = [0] * N
    color = [0] * (N-1)
    for i in range(N-1):
        a,b = LI()
        root[a-1].append((b-1,i))
        root[b-1].append((a-1,i))

    q = [(0,0)]
    ans = 0
    while q:
        i,c = q.pop()
        node[i] = 1
        next_c = 1
        for d,x in root[i]:
            if node[d]: continue
            if next_c == c: next_c += 1
            color[x] = next_c
            ans = max(ans,next_c)
            q.append((d,next_c))
            next_c += 1
    print(ans)
    print(*color,sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):

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

n = int(input())
edge = [[] for _ in [0]*n]
for i in range(~-n):
    a, b = map(int, input().split())
    a -= 1;b -= 1
    edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
    count = 1
    for to, i in edge[now]:
        
        if count == color:
            count += 1
        ans[i] = count
        dfs(to, count)
        count += 1


dfs(0, 0)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()

graph = [[] for _ in range(N)]
edges = []
 
for _ in range(N - 1):
  a, b = inputIL()
  edges.append((a-1, b-1))
  
for a, b in edges:
  graph[a].append(b)
  graph[b].append(a)
  
k = max(len(edges) for edges in graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [ None for _ in range(N) ]
colored = {}

def youcanusethiscolor(u):
  for c in colors:
    if c == usedcolor[u]:
      continue
    yield c
    
for u in range(N):
  color = youcanusethiscolor(u)
  for v in graph[u]:
    if (u,v) not in colored and (v,u) not in colored:
      now = next(color)
      colored[(u,v)] = colored[(v,u)] = now
      usedcolor[v] = now
  
print(k)
for a,b in edges:
  print(colored[(a,b)])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]

col_max = 0
for i in range(N-1):
  a, b = ab[i]
  graph[a] += [b]
  graph[b] += [a]

for i in range(N):
  col_max = max(col_max, len(graph[i]))
print(col_max)

def bfs(s):
  q = deque([s])
  col = [-1]*N
  col[s] = 0
  edge_col = {}

  while q:
    c = 1
    u = q.pop()
    for v in graph[u]:
      if col[v] == -1:
        if c == col[u]:
          c += 1
        col[v] = c
        q.append(v)
        edge_col[(u, v)] = c
        edge_col[(v, u)] = c
        c += 1
  return edge_col

col = bfs(0)

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

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)

    for i in range(N-1):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,i))
        G[b].append((a,i))
    
    res = [0] * (N-1)
    dfs(0,-1,-1,G,res)
    print(max(res))
    print(*res, sep='\n')
    
def dfs(v,p,pc,G,res):
    next_c = 1
    for next_v, num in G[v]:
        if next_v == p:
            continue
        if next_c == pc:
            next_c += 1
        
        res[num] = next_c
        dfs(next_v,v,next_c,G,res)
        
        next_c += 1

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
AB = [[] * 2 for _ in range(n - 1)]
graph = [[] for _ in range(n + 1)]

for i in range(n - 1):
	a, b = map(int, input().split())
	AB[i].append(a)
	AB[i].append(b)
	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

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

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

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N = inputInt()
	ki = [[] for i in range(N)]
	inp = {}
	ans = [inf for i in range(N-1)]
	ansInt = 0

	for i in range(N-1):
		a,b = inputMap()
		a -= 1
		b -= 1
		ki[a].append(b)
		ki[b].append(a)
		inp[(a,b)] = i

	for i in ki:
		if len(i) > ansInt:
			ansInt = len(i)

	for i in range(N):
		ko = ki[i]
		dame = []
		mi = []
		for j in ko:
			
			if i < j:
				mi.append(j)
			else:
				dame.append(ans[inp[(j,i)]])
		
		mark = 0
		for j in mi:
			for ii in range(mark,ansInt+1):
				if ii in dame:
					pass
				else:
					ans[inp[(i,j)]] = ii
					dame.append(ii)
					break
				mark += 1
		

	
	
	

	print(ansInt)
	for i in ans:
		print(i+1)




def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

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

n=int(input())

g =[[] for _ in range(n)]
ans=[0] * (n-1)

def dfs(v,c=-1,p=-1):
    k=1

    for u,ei in g[v]:
        if u == p: continue
        if k == c: k+=1

        ans[ei] = k
        k+=1
        dfs(u,ans[ei],v)

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

dfs(0)
mx=0

for i in range(n):
    mx = max(mx,int(len(g[i])))

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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(20000000)

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

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num,pre_color):
    color_num = -1
    for route in routes[num]:
        color_num += 1
        if color_num == pre_color:
            color_num+=1
        if route_color[route[1]] != -10e+10:
            color_num-=1
            pass
        else:
            route_color[route[1]] = color_num
            
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0],route_color[route[1]])
    return

function(0,-1)
print(max_route)
for color in route_color:
    print(color+1)

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


N = int(readline())
graph = [[] for _ in range(N+1)]
AB = []

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

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

print(max(color))

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

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

from collections import deque

d = deque()
d.append([0, -1])
while d:
    point, prev = d.popleft()
    color = 1 if prev != 1 else 2
    for a, index in graph[point]:
        if ans[index] == 0:
            ans[index] = color
            d.append([a, color])
            color += 1 if prev != color + 1 else 2
print(max(ans))
print(*ans, sep='\n')

Solution (Python):
from collections import deque

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

ans = [0]*(N-1)
q = deque([(0, -1)])
while q:
  v, pc = q.popleft()
  c = 1 if pc != 1 else 2
  for nv, i in G[v]:
    if ans[i] == 0:
      ans[i] = c
      q.append((nv, c))
      c += 1 if c+1 != pc else 2

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

Solution (Python):
from collections import deque

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))
    g[b-1].append((a-1, i))

max_color = 0
for i in range(N):
    max_color = max(max_color, len(g[i]))

res = [-1] * (N-1)
d = [-1] * N
que = deque([])
que.append((0, -1))
d[0] = 0
while que:
    v, c = que.popleft()
    color = 1
    if color == c:
        color += 1
    for f, s in g[v]:
        if d[f] == -1:
            d[f] = d[v] + 1
            que.append((f, color))
            res[s] = color
            color += 1
            if color == c:
                color += 1

print(max_color)
for v in res:
    print(v)

Solution (Python):



import sys



N = int(input())

d = {}
col_self = [0] * N

for i in range(N):
    d[i] = {}

cond = []
for i in range(N-1):
    cond.append(list(map(int, input().split())))
    a, b = cond[i][0]-1, cond[i][1]-1
    d[a][b] = {'cond':i, 'color':0}




colors = []
result = [0] * N

for i in range(N):
    num = len(d[i])
    if col_self[i] > 0:
        num += 1

    if num > len(colors):
        colors = list(range(1, num+1))

    idx = 0
    for node in d[i]:
        if colors[idx] == col_self[i]:
            idx += 1
        d[i][node]['color'] = colors[idx]
        col_self[node] = colors[idx]
        result[d[i][node]['cond']] = colors[idx]
        idx += 1

print(len(colors))

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

Solution (Python):
'''catupper
ポイントA.再帰DFSで全ての頂点をチェックし、辺の色を求める。上限に注意。
ポイントB.入力に注意。
頂点が連結しているということは、そこに辺があるということ。
辺は頂点を結ぶので、辺が連結している二つの頂点(a[i], b[i])で表現され、
まず、辺をedgeに格納する。
辺の色は辞書color_dictに格納している。
辺である(a[i], b[i])をキーとして使って、color_dict[(a[i], b[i])]で
その辺に対応する色の番号が分かるようにしている。
辞書のキーが配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):  
    print(color_dict[(a[i], b[i])])
疑問点：色が新しくなるのは分かるけど、
色が1から再び使えるようになる仕組みは下の通りで良いのか？
'''

import sys
sys.setrecursionlimit(1000000)

n = int(input())
edge = [[] for i in range(n)]

a = [0] * n
b = [0] * n

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

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):


    global k
    color = 1
    
    for to in edge[x]:
    
    
    
    
    
    
    
    
        if to == last:continue
        
        if color == ban_color:color += 1
        
        
        color_dict[(x, to)] = color
        
        
        dfs(to, x, color)
        
        
        
        
        color += 1
        
    k = max(k, color-1)    
    

dfs(0)


print(k)
for i in range(n-1):

    print(color_dict[(a[i], b[i])])
    
    
'''  以下の場合分けは不要。制約で1≤ai<bi≤Nだからか？
無向グラフで、aiで一通り、全ての辺が出力されるから？
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])
'''

Solution (Python):


import sys
input = sys.stdin.readline

import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[[i] for i in range(N-1)]
A_sort =sorted(A)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) 
    connection[b].add(a) 
    A_sort[i].append((a,b))             
A_sort.sort(key=lambda x:x[1])

color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )


aa=[]
hq_none =heapq.heapify(aa)
color_node ={i:[] for i in range(1,N+1)} 
for i in range(1,N+1):
    heapq.heapify(color_node[i])
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A_sort[i][1] 
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(color_node[n_a][0]) -1
    while True:
        
        q,color =divmod(color,(-1)*color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            
            A_sort[i].append((-1)*color+1)     
            heapq.heappush(color_node[n_a],color)    
            heapq.heappush(color_node[n_b],color)    

            break
        else:
            color -=1      

print(color_max)
A_sort.sort()
for i in A_sort:
    print(i[2])

Solution (Python):
'''catupper
ポイントA.再帰DFSで全ての頂点というか、辺をチェック。
ポイントB.入力に注意。頂点の連結が辺になっている。
辺は頂点を結ぶので(a[i], b[i])で表現され、対応する色を
color_dict[(a[i], b[i])]としている。
配列が二重配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):  
    print(color_dict[(a[i], b[i])])
疑問点：色が新しくなるのは分かるけど、
色が1から再び使えるようになる仕組みは下の通りで良いのか？
'''

import sys
sys.setrecursionlimit(1000000)

n = int(input())
edge = [[] for i in range(n)]

a = [0] * n
b = [0] * n

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):


    global k
    color = 1
    
    for to in edge[x]:
    
    
    
    
        if to == last:continue
        
        if color == ban_color:color += 1
        
        
        color_dict[(x, to)] = color
        
        dfs(to, x, color)
        
        
        
        color += 1
        
    k = max(k, color-1)    
    

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

dfs(0)


print(k)
for i in range(n-1):
    print(color_dict[(a[i], b[i])])
'''  以下の場合分けは不要。
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])
'''