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

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIR1(n): return [LI1() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    AB = LIR1(N-1)

    g = [[] for _ in range(N)]
    visited = [False] * N
    ins = [-1] * N

    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    visited[0] = True
    q.append(0)

    while q:
        u = q.popleft()
        outs_num = 0
        visited[u] = True

        for v in g[u]:
            if not visited[v]:
                if outs_num == ins[u]:
                    outs_num += 1

                ins[v] = outs_num

                outs_num += 1
                q.append(v)

    print(max(ins) + 1)
    for a, b in AB:
        print(ins[b] + 1)
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

ans = [0] * (N - 1)
q = deque([[1, 0, -1]])
while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node: continue
        if cnt == pcol: cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1
print(max(ans))
print(*ans, sep="\n")

Solution (Python):
from collections import deque,defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
I = defaultdict(lambda:0)
cs = [0]*n
used = [0]*n
q = deque([0])
used[0]=1
k = 0
while q:
    u = q.popleft()
    if k < len(data[u]):
        k = len(data[u])
    cur = 1
    for v in data[u]:
        if used[v]:continue
        if cur==cs[u]:cur+=1
        cs[v] = cur
        I[(u,v)] = cur
        I[(v,u)] = cur
        cur += 1
        used[v] = 1
        q.append(v)
print(k)
for i,j in sides:
    print(I[(i,j)])

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):
from collections import deque

def nearlist(N, LIST):  
    NEAR = [[] for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].append(b - 1)
        NEAR[b - 1].append(a - 1)
    return NEAR


def bfs(NEAR, S, COLOR, ANS):  
    
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        c, cnt = COLOR[q], 0
        for i in NEAR[q]:  
            if i in frag:  
                continue
            cnt += 1 + (cnt == c - 1)
            COLOR[i] = cnt
            ANS[(q, i)], ANS[(i, q)] = cnt, cnt
            que.append(i), frag.add(i)
    return


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

color, ans = [-1] * n, {}
near = nearlist(n, ab)
bfs(near, 0, color, ans)
print(max(ans.values()))
for a, b in ab:
    print(ans[(a - 1, b - 1)])

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

stack = deque([0])
stack.append(0)
ans = [0 for _ in range(n)]
while stack:
    v = stack.popleft()
    c = 1
    for nv in g[v]:
        if ans[v] == c:
            c += 1
        ans[nv] = c
        c += 1
        stack.append(nv)

print(max(ans))
for i in e:
    print(ans[i])

Solution (Python):
from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    e.append(b-1)
 
q=deque([0])
 
color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1
 
        color[x]=c
        c+=1
        q.append(x)
 
print(max(color))
for i in e:
    print(color[i])

Solution (Python):


n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)

for i in range(n):
    cand1,cand2=set(),[]
    
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])

Solution (Python):
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)

for i in range(n):
    cand1,cand2=set(),[]
    
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])

Solution (Python):
from collections import deque

def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for i in range(1,n):
    a,b = map(int, input().split())
    d1 = {"id":i,"to":b}
    d2 = {"id":i,"to":a}
    graph[a].append(d1)
    graph[b].append(d2)
  
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[[] for _ in range(n+1)]
  reached=[False]*(n+1)
  ans=[0]*(n)
  while q:
    current = q.popleft()
    reached[current] = True
    temp = 1
    for dic in graph[current]:
      id = dic["id"]
      next = dic["to"]
      if reached[next]:
        continue
      while temp in color[current]:
        temp += 1
      color[next].append(temp)
      ans[id] = temp
      temp += 1
      q.append(next)
  for i in ans[1:]:
    print(i)
      
if __name__ == '__main__':
  main()

Solution (Python):

import sys
sys.setrecursionlimit(200_000)

def solve(N: int, a: "List[int]", b: "List[int]"):
    from itertools import count
    edges = [[] for _ in range(N)]
    for i, (aa, bb) in enumerate(zip(a, b)):
        edges[aa-1].append((bb-1, i))
        edges[bb-1].append((aa-1, i))
    ans = [None] * (N-1)
    visited = set()
    def dfs(n, c):
        if n in visited:
            return
        visited.add(n)
        for (nn, i), cc in zip(filter(lambda x: x[0] not in visited, edges[n]),
                          filter(lambda y: y != c, count(1))):
            ans[i] = cc
            dfs(nn, cc)
    dfs(0, None)
    return [max(ans)] + ans


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N - 1)  
    b = [int()] * (N - 1)  
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(N, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

def dfs(x, last=-1, ban_color=-1):
    """
    x: 今いる頂点
    last: 既に探索済の頂点(無限ループにならないように初期値-1)
    ban_color: 既に探索済の頂点(last)と今いる頂点(x)との辺に塗られている色(→使っちゃいけない色)
    """
    color = 1
    for to in vertex[x]:  
        if to == last: continue  
        if color == ban_color: color += 1
        color_dic[(x, to)] = color  
        dfs(to, x, color)
        color += 1
        
        

n = int(input())
vertex = {i: [] for i in range(n)} 
a = [0] * (n - 1)  
b = [0] * (n - 1)  
color_dic = {} 


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

max_v = 0

for _, v in vertex.items():
    if len(v) > max_v:
        max_v = len(v)
print(max_v)
    


dfs(0)

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

Solution (Python):
import sys 
from collections import deque,defaultdict
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 i in range(N-1):
    a,b = map(int,readline().split())
    AB.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * (N+1)
dist[1] = 0
COL = defaultdict()
q = deque([(1,0)])
max_col = 0

def bfs(max_col):
    while q:
        x,pre_col = q.popleft()
        c = 1
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            if c == pre_col:
                c += 1
            COL[(x,nx)] = c
            dist[nx] = 1
            q.append((nx,c))
            max_col = max(max_col,c)
            c += 1
    return max_col  

max_col = bfs(max_col)
print(max_col)
for a,b in AB:
    if (a,b) in COL:
        print(COL[(a,b)])
    else:
        print(COL[(b,a)])

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)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





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

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

pos = deque([0])
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 i in ans:
    print(i)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N = NI()
    edges = [NLI() for _ in range(N-1)]
    graph = [[] for _ in range(N+1)]
    edge_dict = {}
    for i, edge in enumerate(edges):
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        edge_dict[(edge[0], edge[1])] = i+1

    queue = deque()
    queue.append(1)
    seen = [0]*(N+1)
    colors = [-1] * N
    colors[1] = 1
    now_colors = deque()
    now_colors.append(-1)
    while queue:
        now = queue.popleft()
        now_color = now_colors.popleft()
        seen[now] = 1
        nexts = graph[now]
        color = 1
        for goto in nexts:
            if seen[goto] == 0:
                a, b = min(now, goto), max(now, goto)
                if color == now_color:
                    color += 1
                colors[edge_dict[(a, b)]] = color
                queue.append(goto)
                now_colors.append(color)
                color += 1
    print(max(colors))
    for i in range(1, N):
        print(colors[i])



if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

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
    
answer = []
for a, b in AB:
  if parent[a] == b:
    answer.append(color[a])
  else:
    answer.append(color[b])
K =max(answer)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a,b in ab:
	print(color[(a-1, b-1)])

Solution (Python):
import sys
from io import StringIO
import unittest
import os
from collections import deque


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    n = int(input())
    ab_s = [list(map(int, input().split())) for i in range(n - 1)]

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

    for ab in ab_s:
        ref_s[min(ab)].append(max(ab))

    
    que = deque()
    que.appendleft((1, 0))  

    ans = {}
    
    while len(que) is not 0:

        pop = que.pop()
        parent = pop[0]
        parent_col = pop[1]

        child_col = 0

        
        for child in ref_s[parent]:

            child_col += 1
            if child_col == parent_col:
                child_col += 1

            key1 = min(parent, child)
            key2 = max(parent, child)

            
            
            if ans.get((key1, key2), 0) != 0:
                continue

            
            ans[(key1, key2)] = child_col

            
            
            que.appendleft((child, child_col))

    
    print(max(ans.values()))

    
    for ab in ab_s:
        key1 = min(ab[0], ab[1])
        key2 = max(ab[0], ab[1])
        print(ans.get((key1, key2)))



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2
2 3"""
        output = """2
1
2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """8
1 2
2 3
2 4
2 5
4 7
5 6
6 8"""
        output = """4
1
2
3
4
1
1
2"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """6
1 2
1 3
1 4
1 5
1 6"""
        output = """5
1
2
3
4
5"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.pop()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

def coloring(n, previous, col): 
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col 
		else:
			if cnt == col:
				cnt += 1
			color[(x, n)] = cnt
			color[(n, x)] = cnt
			coloring(x, n, cnt)
			cnt += 1

coloring(0, -1, 0)

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

Solution (Python):



from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0:
        cur = q.popleft()
        col = 1
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

N = int(input())
P = [[] for _ in range(N)]
AB = defaultdict(int)

for _ in range(N-1):
  a, b = map(lambda x: int(x)-1, input().split())
  P[a].append(b)
  P[b].append(a)
  AB[(a, b)] = -1

C = [-1] * N

def bfs(s):
    d = [-1] * N
    d[s] = 0
    p_old = [s]
    K = -1
    while p_old:
      p_new = []
      for i in p_old:
        c = 1
        for j in P[i]:
          if d[j] != -1:
            continue
          if C[i] == c:
            c += 1
          d[j] = 0
          p_new.append(j)
          C[j] = c
          AB[(i, j)] = c
          K = max(K, c)
          c += 1
      p_old = p_new
    return K

print(bfs(0))

for x in AB.values():
  print(x)

Solution (Python):
N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

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

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)
K = -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
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

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

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

Solution (Python):
N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

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

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)
K = -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
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

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

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

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

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

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

Solution (Python):


import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    to = list()
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
        to.append(b)
    l = [-1] * n
    l[0] = 10**10
    q = deque([0])
    while q:
        v = q.popleft()
        vcolor = l[v]
        for i, w in enumerate(g[v]):
            q.append(w)
            if i < vcolor:
                l[w] = i
            else:
                l[w] = i + 1

    print(max(l[1:])+1)
    for i in to:
        print(l[i]+1)



if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict, deque


N, *AB = map(int, open(0).read().split())
g = defaultdict(set)
edges = []
for a, b in zip(*[iter(AB)] * 2):
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)
    edges.append((a, b))

q = deque([0])
visited = [False] * N
visited[0] = True
used = [0] * N
colors_cnt = 1
ans = {}
while q:
    v = q.popleft()
    color = 1
    for nv in g[v]:
        if visited[nv]:
            continue
        if color == used[v]:
            color += 1
        used[nv] = color
        ans[(min(v, nv), max(v, nv))] = color
        color += 1
        q.append(nv)
        visited[nv] = True
    colors_cnt = max(colors_cnt, color - 1)
print(colors_cnt)
[print(ans[(a, b)]) for a, b in edges]