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
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ab = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n-1)]
    tmd = collections.defaultdict(list)
    tmdd = collections.defaultdict(int)
    m_in = 0
    m_no = -1
    for a, b in ab:
        tmd[a] += [b]
        tmd[b] += [a]
        tmdd[a] += 1
        tmdd[b] += 1
    cnt = 0
    for k, v in tmdd.items():
        if v > m_in:
            m_in = v
            m_no = k
        elif v == m_in:
            cnt += 1
    m_in = m_in + 1 if cnt == len(tmd) - 1 and len(tmd) == 3 else m_in

    ql = [[0, m_no]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[m_no]
    aq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            ls = []
            limit = tmdd[tmp]
            for i in range(1, m_in + 1):
                if i != cost:
                    ls.append(i)
                if len(ls) >= limit:
                    break
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    p = ls.pop()
                    ql.append([p, tmv])
                    fq[tmv]
                    aq[tmp, tmv] = p
                    aq[tmv, tmp] = p
        else:
            break
    print(m_in)
    for a, b in ab:
        print(aq[a, b])


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math



sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tree = defaultdict(list)
    

    for i, (a, b) in enumerate(ab):
        
        
        
        if a not in tree:
            tree[a] = []
        tree[a].append((b, i))

    
    
    
    
    
    
    
    
    
    

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tree[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

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

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].add(b)
        E[b].add(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        a, v = Q.popleft()
        c = 0
        for u in E[v]:
            E[u].remove(v)
            c += 1
            if c == a:
                c += 1
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)
        E[v] = set()
    print(K)
    print("\n".join(A))

main()

Solution (Python):

n = int(input())
color = [None for i in range(n)]
tree = {}
res = 0
et = []
for i in range(n-1):
    u, v = [int(x) for x in input().strip().split()]
    et.append((u,v))
    if u not in tree:
        tree[u] = []
    if v not in tree:
        tree[v] = []
    tree[u].append(v)
    tree[v].append(u)
    res = max(res, len(tree[u]),len(tree[v]))





edge = {}
color[0] = 0

for i in range(1,n+1):
    for v in tree[i]:
        if v>i:
            tc = color[i-1]+1
            if tc>res:
                tc = tc%res
            color[i-1] = tc
            color[v-1] = tc
            if i not in edge:
                edge[i] = {}
            if v not in edge[i]:
                edge[i][v] = {}
            edge[i][v] = tc


print(res)
for e in et:
    print(edge[e[0]][e[1]])

Solution (Python):
import queue
n = int(input())

tree = [[] for i in range(n)]
edges = []

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


ncol = max([len(tree[i]) for i in range(n)])
usedcol = [-1 for i in range(n)]
colour = [dict() for i in range(n)]


visited = [False for i in range(n)]
def bfs(v):
    q = queue.Queue(0)
    q.put(v)
    while not q.empty():
        v = q.get()
        visited[v] = True
        u = usedcol[v]
        col = 0
        
        for i in range(len(tree[v])):
            nv = tree[v][i]
            if not visited[nv]:
                col += 1; col += 1 if col==u else 0
                usedcol[nv] = col
                colour[v][nv] = col; colour[nv][v] = col
                q.put(nv)

bfs(1)
print(ncol)
for (a,b) in edges:
    print(colour[a][b])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    a -= 1
    b -= 1
    query[a].append((b,i))
    query[b].append((a,i))
  ans = 0
  for i in range(n):
    ans = max(ans,len(query[i]))
  print(ans)
  node = deque([])
  stack = [[] for _ in range(n)]
  for i in range(n):
    if len(query[i]) == ans:
      node.append((i,ans,100000))
      break
  for i in range(n):
    stack[i] = (len(query[i]))
  
  tmp = [-1]*(n-1)
  visit = [False]*n
  while node:
    
    place,maxnode,last = node.popleft()
    donotuse = [last]
    for j,i in query[place]:
        if tmp[i] == -1:
          while maxnode in donotuse:
            maxnode -= 1
            if maxnode <= -1:
              maxnode = ans
          tmp[i] = maxnode
          donotuse.append(maxnode)
          maxnode -= 1
        
        if visit[j]:
          continue
        else:
          node.append((j,stack[j],tmp[i]))
    visit[place] = True
    
    
  for i in tmp:
    print(i)
solve()

Solution (Python):
import collections

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



max_e = max(counter)
colors_node = [-1 for _ in range(n + 1)]

edges.sort(key = lambda x: (x[1], x[2]))

colors = [-1 for _ in range(n + 1)]
cnt = 1
origin = -1
for i in range(n - 1):
	if origin == edges[i][1]:
		cnt += 1
	else:
		cnt = 1
		origin = edges[i][1]

	edges[i].append((colors[edges[i][1]] + cnt) % max_e)
	colors[edges[i][2]] = (colors[edges[i][1]] + cnt) % max_e

print(max_e)
edges.sort(key = lambda x: x[0])
for i in range(n - 1):
	print(edges[i][3] + 1)

Solution (Python):
from collections import deque

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

print(max(map(len, nl)))

ans = [-1 for _ in range(N - 1)]
q = deque()
q.append((1, -1, -1))
while len(q) > 0:
    v, p, pc = q.popleft()
    color = 1
    for next_v, i in nl[v]:
        if next_v == p:
            continue
        if color == pc:
            color += 1
        ans[i] = color
        q.append((next_v, v, color))
        color += 1
for a in ans:
    print(a)

Solution (Python):
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append((b-1,i))
    l[b-1].append((a-1,i))
from collections import deque
q=deque([(AB[0][0]-1,1),(AB[0][1]-1,1)])
e[0]=1
M=1
while q:
    vp,c=q.popleft()
    x=1
    for vn,en in l[vp]:
        if e[en]==0:
            if x==c:
                x=c+1
            q.append((vn,x))
            e[en]=x
            M=max(M,x)
            x+=1
print(M)
print(*e,sep='\n')

Solution (Python):
from collections import deque

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

def bfs(tree, idx, mx_color, n):
    queue = deque([])
    queue.append([idx, n, color+1])
    edge_color = {}
    visit = [False] * (n)
    visit[idx] = True

    while queue:
        parent,p,cc = queue.popleft()

        res_color =  my_index(tree[parent], p, -1)+1
        for i, child in enumerate(tree[parent]):
            if visit[child]:
                continue
            child_color = res_color if i+1 == cc else (i+1)
            edge_color[str(min(parent,child))+','+str(max(parent,child))] = child_color

            queue.append([child, parent, child_color])
            visit[child] = True
    return edge_color

n = int(input())
tree = [[] for _ in range(n)]
edge = []
for _ in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    edge.append(str(min(a,b))+','+str(max(a,b)))
color = max(len(i) for i in tree)

edge_color = bfs(tree, 0, color, n)
print(color)

[print(edge_color[c]) for c in edge]

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()

    g = {}
    t = {}
    ans = [1] * (n-1)
    k = [0] * (n+1)

    for i in range(n-1):
        a, b = LMIIS()
        if a in g:
            g[a].append(b)
        else:
            g[a] = [b]
        if b in g:
            g[b].append(a)
        else:
            g[b] = [a]
        t[index(a, b)] = i

    q = deque([[1, g[1][0]]])

    while len(q) > 0:
        a, b = q.pop()
        used = ans[t[index(a,b)]]
        if k[a] == 0:
            k[a] = 1
            color = 1
            for x in g[a]:
                if color == used:
                    color += 1
                if x == b:
                    continue
                ans[t[index(a, x)]] = color
                color += 1
                q.append([a,x])

        if k[b] == 0:
            k[b] = 1
            color = 1
            for x in g[b]:
                if color == used:
                    color += 1
                if x == a:
                    continue
                ans[t[index(b, x)]] = color
                color += 1
                q.append([b,x])

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












if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
data = [0]*(N-1)
cho = [0]*(N+1) 
res = [0]*(N-1) 
for i in range(0,N-1):
    di = list(map(int, input().split()))
    di.append(i)
    data[i] = di

data = sorted(data)
for i in range(0,N-1):
    if i != 0 and data[i][0] == data[i-1][0]:
        cur += 1
    else:
        cur = 1
    if cur == cho[data[i][0]]: cur += 1
    res[data[i][2]] = cur
    cho[data[i][1]] = cur

print(max(cho))
for item in res:
    print(item)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(200000)

def decide_col(colors, edges, node, org, excl_color,max_col):
    if len(edges[node]) > 1:
        i = 1
        for elem in edges[node]:
            next_node = elem[0]
            ind = elem[1]
            if next_node != org:
                while i == excl_color:
                    i = i%max_col + 1
                colors[ind] = i
                decide_col(colors, edges, next_node, node, i,max_col)
                i += 1
    

def det_color(N,edges,start,max_col):
    colors = [0]*(N-1)
    i=1
    for elem in edges[start]:
        node = elem[0]
        ind = elem[1]
        colors[ind] = i
        decide_col(colors, edges, node, start, i, max_col)
        i += 1
    return colors
        

N = int(input())
edges = {}
edge_list = []

for i in range(N):
    edges[i] = []
count = [0]*N

for i in range(N-1):
    A, B = map(int,input().split())
    edge_list.append([A-1,B-1])
    edges[A-1].append([B-1,i])
    edges[B-1].append([A-1,i])
    count[A-1] += 1
    count[B-1] += 1

max_col = max(count)
print(max_col)
start_ind = np.argmax(count)
if type(start_ind)==list:
    start = start_ind[0]
else:
    start = start_ind
colors = det_color(N,edges,start,max_col)

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

Solution (Python):
from collections import defaultdict as dd, Counter
N = int(input())
edges = [None] * (N-1)
es = dd(dict)
for i in range(N-1):
    a, b = map(int, input().split())
    es[a][b] = es[b][a] = i

q = []
q.append((1, -1))
while q:
    i, used = q.pop()
    color = 0
    for to, eid in es[i].items():
        if edges[eid] is not None:
            continue
        color += 1
        if color == used:
            color += 1
        edges[eid] = color
        q.append((to, color))

ct = Counter(edges)
print(len(ct))
for e in edges:
    print(e)

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


n = int(input())
routes = []
dic = [{}] * n
edges = [[]for _ in range(n)]
used = [0]*n

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

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        dic[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(dic[_from][to])

Solution (Python):
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
count = [0]*N
ans = [0]*(N-1)
closed = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1, b-1])
    node[a-1].append(i)
    node[b-1].append(i)
    count[a-1] += 1
    count[b-1] += 1

K = max(count)
print(K)

queue = deque([[0,K+1]])


while queue:
    q,m = queue.popleft()
    p = 1
    for i in node[q]:
        if p == m:
            p += 1
        if ans[i] == 0:
            ans[i] = p
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if closed[next] == 0:
                queue.append([next,p])
                closed[next] = 1
            p += 1

for i in ans:
    print(i)

Solution (Python):
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    ab = [list(map(int, input().split())) for i in range(n - 1)]
    
    
    e = [[] for i in range(n + 1)]
    ansl = {}
    for i in range(n-1):
        a, b = ab[i]
        e[a].append(b)
        ansl[(a,b)] = 0

    d = defaultdict(int)
    for i in range(n-1):
        a, b = ab[i]
        d[a] += 1
        d[b] += 1
    ans = 0
    for i in d.keys():
        ans = max(ans, d[i])
    print(ans)

    
    
    col = [-1 for i in range(n+1)]
    def f(v, c):
        col[v] = 1
        t = 1
        for i in e[v]:
            if col[i] == -1:
                if t == c:
                    t+=1
                ansl[(v,i)] = t
                
                f(i, t)
                t+=1
    f(1,0)
    
    
    
    for i in range(n - 1):
        a, b = ab[i]
        print(ansl[(a,b)])



    

    

    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
P = [[] for _ in range(N + 1)]
AB = []
for _ in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    P[a].append(b)
    P[b].append(a)
    AB.append((a,b))
C = 0

for p in P:
    if len(p) > C:
        C = len(p)


P2 = dict()
def f(n, pre, used):
    c = 1
    for i, next_n in enumerate(P[n]):
        if pre == next_n: continue
        if c == used: c += 1
        
        
        if n > next_n:
            a, b = next_n, n
        else:
            b,a = next_n, n
        P2[(a,b)] = c
        f(next_n, n, c)
        c += 1


print(C)
f(1, -1, 0)
for ab in AB:
    print(P2[ab])

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

n = int(input())
ab = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    ab[a].append([b, i])
    ab[b].append([a, i])
re = [False] * n
ed = [0]*(n-1)


def c(i=0, used=-1):
    global re, ed
    if re[i]:
        return 0
    re[i] = True
    k = 1
    for j in ab[i]:
        if re[j[0]]:
            continue
        if k == used:
            k += 1
        ed[j[1]] = k
        c(j[0], k)
        k += 1


c()
print(max(ed))
print(" ".join([str(i) for i in ed]))

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(N-1):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    T = dict()
    for i in range(N-1):
        T[(a[i]-1, b[i]-1)] = i
        T[(b[i]-1, a[i]-1)] = i
    q = [0]
    cn = max([len(g) for g in G])
    visited = [False] * N
    C = [0] * (N-1)
    while len(q) > 0:
        p = q.pop()
        visited[p] = True
        adj = G[p]
        v = None
        for a in adj:
            if visited[a]:
                v = a
        if v != None:
            ex = C[T[(v, p)]]
        else:
            ex = -1
        counter = 1
        for a in adj:
            if counter == ex:
                counter += 1
            if a != v:
                j = T[(a, p)]
                C[j] = counter
                counter += 1
        for a in adj:
            if not visited[a]:
                q.append(a)
    print(cn)
    for c in C:
        print(c)
    return



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

if __name__ == '__main__':
    main()

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

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

G = defaultdict(list)

v = [-1 for _ in range(N - 1)]

for i, (a, b) in enumerate(ab):
    G[a].append((b, i))
    G[b].append((a, i))

def check(p, trg, pc):
    
    c = 0
    for next_, vi in G[trg]:
        if next_ != p:
            if c == pc:
                c += 1
            check(trg, next_, c)
            v[vi] = c
            c += 1

check(0, 1, -1)
print(len(set(v)))
for c in v:
    print(c + 1)

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

Cs = [0] * (N + 1)
Tr = [[] for _ in range(N + 1)]
for i in range(N - 1):
    Cs[ABs[i][0]] += 1
    Cs[ABs[i][1]] += 1
    p = min(ABs[i][0], ABs[i][1])
    c = max(ABs[i][0], ABs[i][1])
    Tr[p].append((c, i))
K = max(Cs)
print(K)

import collections

d = collections.deque()
d.append(1)

Pc = [0] * (N + 1)
Nc = [1] * (N + 1)
ABsc = [0] * (N + 1)
Cis = [1] * N
while (len(d) > 0):
    p = d.popleft()
    for (c, i) in Tr[p]:
        d.append(c)
        col = Nc[p]
        if Pc[p] == col:
            col += 1
        Nc[p] = col + 1
        Pc[c] = col
        Cis[i] = col

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

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
degree = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_color = [0 for i in range(n)]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append([b,i])
    degree[a] += 1
    degree[b] += 1


maxcolor = max(degree)
search_list = [0]
node_color[0] = 0
color_list = [ k for k in range(1,maxcolor+1) ]

while search_list:
    new_search_list = []
    for i in search_list:
        p = 0
        for j, v in enumerate(connect_list[i]):
            a, b = v
            new_search_list.append(a)
            if node_color[i] == color_list[p]:
                p += 1
            node_color[a] = color_list[p]
            connect_list[i][j] = [b,color_list[p]]
            p += 1
    search_list = new_search_list

ans_list = []
for i in connect_list:
    for j in i:
        ans_list.append(j)

ans_list.sort()
print(maxcolor)
for i in ans_list:
    print(i[1])

Solution (Python):
from collections import deque

N = int(input())
L = []
dic = {}
E = [[] for _ in range(N)]
e = [0]*(N)
for i in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    e[a-1] += 1
    e[b-1] += 1
    L.append((a-1, b-1))
    
K = max(e)
print(K)

q = deque()
q.append((0, -1))
used = [0]*N
used[0] = 1
while q:
    t = q.popleft()
    num = 1
    for v in E[t[0]]:
        if used[v] == 0:
            used[v] = 1
            q.append((v, (t[1]+num)%K))
            if t[0] < v:
                dic[(t[0], v)] = (t[1]+num)%K+1
            else:
                dic[(v, t[0])] = (t[1]+num)%K+1
            num += 1
                
for i in range(N-1):
    print(dic[L[i]])

Solution (Python):
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
p, k = d.pop()
ans = [None] * (N - 1)
Q = collections.deque([(p, 0)])
while Q:
    p, fr = Q.popleft()
    color = 1
    for i in s[p]:
        if ans[i] is None:
            if color == fr:
                color += 1
            ans[i] = color
            Q += [(A[i] + B[i] - p, color)]
            color += 1
print(k)
print('\n'.join(map(str, ans)))

Solution (Python):
from collections import deque
N = int(input())
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
tree = [[] for _ in range(N)]
for n, (i, j) in enumerate(X):
    graph[i - 1].append(j - 1)
    graph[j - 1].append(i - 1)
    
    tree[i - 1].append((n, j - 1))
    
K = max(len(x) for x in graph)
q = deque()
q.append((0, 0))
ans = [0] * (N - 1)

while len(q) > 0:
    
    u, c = q.popleft()
    
    cnt = 1
    for i, (n, v) in enumerate(tree[u]):
        if cnt == c:
            cnt += 1

        ans[n] = cnt
        q.append((v, cnt))
        cnt += 1
        
print(K)
print(*ans, sep="\n")

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


n = int(input())
dg = 10**6
edge = [[] for _ in [0]*n]
hen = []


for _ in [0]*(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    hen.append((a-1)*dg+b-1)

p = -1
q = -1
for i in range(n):
    if p < len(edge[i]):
        p = max(p,len(edge[i]))
        q = i

par = [-2]*n
chi = [[] for _ in [0]*n]
tank = []
new = [q]
par[q] = -1

while len(new) != 0:
    tank = []
    for e in new:
        for ch in edge[e]:
            if par[ch] < -1:
                par[ch] = e
                chi[e].append(ch)
                tank.append(ch)
    new = tank


co = [0]*n
new = [q]
while len(new) != 0:
    tank = []
    for e in new:
        color = 1
        for ch in chi[e]:
            if color == co[e]:
                color += 1
            co[ch] = color
            color += 1
            tank.append(ch)
    new = tank

print(p)
for e in hen:
    a,b = e//dg,e%dg
    if par[a] == b:
        print(co[a])
    else:
        print(co[b])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]

mx = 0
used = [set() for i in range(N)]
ans = [0] * (N-1)
cnt = 0
for u in range(N):
    mx = max(mx, len(nodes[u]))
    color = 1
    for v in nodes[u]:
        a, b = min(u, v), max(u, v)
        if edges[(a, b)][1] == -1:
            while color in used[a] or color in used[b]:
                color += 1
            edges[(a, b)][1] = color
            used[a].add(color)
            used[b].add(color)
            i = edges[(a, b)][0]
            ans[i] = str(color)
            color += 1
            cnt += 1
            if cnt == N-1:
                break
    else:
        continue
    break
print(mx)
print('\n'.join(ans))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return "".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(a,b,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2
        if ll == mid:
            return ll
        co = mid * a
        mm = mid
        while mm != 0:
            co += b
            mm //= 10 
        if co >= r:
            rr = mid-1
        else:
            ll = mid


n = onem()

kkk = [[] for i in range(n)]

for i in range(n-1):
    a,b = m()
    kkk[a-1].append([b-1,i+1])
    kkk[b-1].append([a-1,i+1])
de = cl.deque([[0,0,0]])
kk= []
while de:
    j,k,p = de.popleft()
    co = 1
    for i in range(len(kkk[j])):
        if not kkk[j][i][0] == k:
            if co == p:
                co += 1
            de.append([kkk[j][i][0],j,co])
            kk.append([co,kkk[j][i][1]])
            co += 1

kk.sort(key = lambda x:x[1])

print(max(kk,key = lambda x:x[0])[0])

for i in range(n-1):
    print(kk[i][0])

Solution (Python):
from collections import deque

def read():
    N = int(input().strip())
    G = [list() for _ in range(N+1)]
    H = [list() for _ in range(N+1)]
    pairs = []
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
        H[a].append(i)
        H[b].append(i)
    return N, G, H

def paint_edges(N, G, max_edges, H):
    C = [-1 for _ in range(N-1)]
    q = deque()
    q.appendleft((1, -1))
    while(len(q) > 0):
        s, c = q.pop()
        for i in range(len(G[s])):
            t = G[s][i]
            idx = H[s][i]
            if C[idx] == -1:
                c = (c + 1) % max_edges
                C[idx] = c
                q.append((t, c))
    return C


def solve(N, G, H):
    max_edges = 0
    for i in range(N):
        max_edges = max(max_edges, len(G[i]))
    C = paint_edges(N, G, max_edges, H)
    return max_edges, C

if __name__ == '__main__':
    inputs = read()
    max_edges, C = solve(*inputs)
    print(max_edges)
    for c in C:
        print(c+1)

Solution (Python):
from collections import deque

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
already = [1] * n 
k = 0
ans = [0] * (n-1)
queue = deque([0])
parent_colors = deque([0])

for index,(a,b) in enumerate(ab):
  a -= 1
  b -= 1
  tree[a].append((index,b))
  tree[b].append((index,a))
while len(queue):
  now = queue.popleft()
  
  if already[now]:
    already[now] = 0
    color = 1
    parent_color = parent_colors.popleft()
    for index,i in tree[now]:
      if already[i]:
        if color == parent_color:
          color += 1
        ans[index] = color
        parent_colors.append(color)
        color += 1
        queue.append(i)
         
print(max(ans))
for i in ans:
  print(i)

Solution (Python):
N = int(input())

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

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

for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque

ans = []
col_max = 1
q = deque([(0, -1, 0)])
while len(q) > 0:
    col = 1
    src, prev, col_prev = q.popleft()
    
    for dst in graph[src]:
        if dst == prev: continue
        
        if col == col_prev: col += 1
        
        
        ans.append((dst, src, col))
        q.append((dst, src, col))
        col_max = max(col, col_max)
        col += 1
        
ans.sort(key=lambda x: x[0] * N + x[1])
        
print(col_max)
for ai, bi in ab:
    l = 0
    r = N - 2
    
    while l < r:
        m = l + (r - l + 1) // 2
        tmp = ans[m][0] * N + ans[m][1]
        
        if tmp <= (bi - 1) * N + (ai - 1):
            l = m
        else:
            r = m - 1
    
    
    print(ans[l][2])

Solution (Python):
import sys
sys.setrecursionlimit(100010)
n=int(input())
edge=[]
G=[[] for _ in range(n+1)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edge.append([x,y])
    G[x].append(_)
    G[y].append(_)
k=0
root=0
for i in range(1,n+1):
    if k<len(G[i]):
        root=i
        k=len(G[i])
co=[1 for i in range(n+1)]
vis=[False for i in range(n+1)]
def dfs(node,lastco=-1):
    tmp=lastco
    for v in G[node]:
        if not vis[v]:
            tmp+=1
            co[v]=tmp%k
            vis[v]=True
            if node==edge[v][0]:
                dfs(edge[v][1],co[v])
            else:
                dfs(edge[v][0],co[v])

dfs(root)
print(k)
for i in range(n-1):
    print(co[i]+1)