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 copy

n=int(input())
org_set=set([i for i in range(1,10**5)])
edges=[]
relations={}
nodes=[]
for i in range(n-1):
    a,b=map(int,input().split(" "))
    edges.append([a,b])
    relations.setdefault(a,[]).append(b)
    nodes.append([])
nodes.append([])
nodes.append([])

max_color=0
for start in range(1,n+1):
    targets=relations.get(start,[])
    color=1
    for target in targets:
        if color in nodes[start]:
            color+=1
        else:
            pass
        nodes[target].append(color)
        if color>=max_color:
            max_color=color
        color+=1

print(max_color)
for edge in edges:
    print(nodes[edge[1]][0])

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


n = int(input())
ans = [0]*(n-1)
edges = [[]for _ in range(n)]
used = [0]*n

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

for node in range(n):
    unable = used[node]
    color = 1

    for to, id in edges[node]:
        if color == unable:
            color += 1
        ans[id] = color
        used[to] = color
        color += 1

print(max(used))
for color in ans:
    print(color)

Solution (Python):
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    color=[-1]*n
    color[0]=0
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    d=[-1]*n
    d[0]=0
    q=[0]
    cnt=0
    while q:
        qq=[]
        cnt+=1
        while q:
            i=q.pop()
            for j in g[i]:
                if d[j]==-1:
                    d[j]=cnt
                    qq.append(j)
        q=qq
    print(max(color[1:]))
    for i,j in ab:
        if d[i-1]>d[j-1]:
            k=i
        else:
            k=j
        print(color[k-1])
main()

Solution (Python):
N = int(input())
edge = {}
tree = [[] for i in range(N)]
colors = [1]*(N-1)
c_p = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    tree[a].append(b)
    edge[(a,b)] = i

for i in range(N):
    c = 1
    for v_c in tree[i]:
      while c in c_p[i]: c+=1
      colors[edge[(i,v_c)]] = c
      c_p[v_c].append(c)
      c+=1

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

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
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    graph[a].append((b,i))
    graph[b].append((a,i))
    edge.append((a,b,i))

m = 0
for i in range(n):
    m = max(m,len(graph[i]))

print(m)
ans = [None]*(n-1)
que = deque()
que.append((0,0))
while que:
    v,color = que.popleft()
    cnt = 1
    for u,i in graph[v]:
        if ans[i] == None:
            if cnt != color:
                ans[i] = cnt
                que.append((u,cnt))
                cnt += 1
            else:
                ans[i] = cnt+1
                que.append((u,cnt+1))
                cnt += 2
print(*ans)

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

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

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

N = int(input())

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






R = [None for i in range(N)]
def dfs(using, cur):
    R[cur] = using
    i=0
    for t in T[cur]:
        if i==using:
            i+=1
        dfs(i,t)
        i+=1


dfs(-1, 0)

print(max(R)+1)

for e in E:
    print(R[e[1]]+1)

Solution (Python):
import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

q = collections.deque([(id, 0)])
print(max_e)
d = dict()
for a, b in ab:
    d[(a-1, b-1)] = 0
    d[(b-1, a-1)] = 0
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        d[(x, y)] = i
        d[(y, x)] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

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

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

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

data = [None] * (n - 1)


edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data[i] = [a, b]
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

max_node = 0

finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i

k = len(adjacent_list[max_node])

def dfs(node, num):
    
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    
    color_list = [i for i in range(1,len(node_list) + 2) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        
        if i not in finished:
            
            
            
            edgedata[(min(node, i), max(node, i))] = color_list[c_i]
            
            dfs(i, color_list[c_i])
            
            c_i += 1

dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])

Solution (Python):
def d_coloring_edges_on_tree():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    
    tree = {i: dict() for i in range(N)}
    for a, b in Edges:
        tree[a - 1][b - 1] = -1
        tree[b - 1][a - 1] = -1

    k = max(len(tree[a]) for a in range(N))  
    used_color = [-1] * N
    used_color[0] = k - 1

    q = deque([0])
    while q:
        current = q.pop()
        color_current = used_color[current]  
        for child in tree[current].keys():
            if used_color[child] != -1:
                continue  
            color_current = (color_current + 1) % k
            tree[current][child] = color_current
            tree[child][current] = color_current
            used_color[child] = color_current
            q.appendleft(child)

    ans = [k] + [tree[a - 1][b - 1] + 1 for a, b in Edges]
    return ' '.join(map(str, ans))

print(d_coloring_edges_on_tree())

Solution (Python):
from collections import deque

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

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

A = [0] * (N - 1)
Q = deque([1])
while Q:
    p, v = divmod(Q.popleft(), N + 1)
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append(c * (N + 1) + u)
        A[i] = c

print(max(A))
print("\n".join(map(str, A)))

Solution (Python):
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        t = 1
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

A = [0] * (N - 1)
Q = deque([(0, 1)])
while Q:
    p, v = Q.popleft()
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[i] = c

print(max(A), *A)

Solution (Python):


import sys
 
n = int(sys.stdin.readline().strip())
adj = [set() for _ in range(n)]
colors = dict()
edges = []
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    edges.append([a, b])
 
col = max(len(v) for v in adj)
 
s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break
 
Q = [[s, -1, -1]]
while Q:
    cur, prev, prev_color = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == prev_color:
            c += 1
        colors[min(cur, nex)*n + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in edges:
    print(colors[a*n + b])

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)

queue = deque()
queue.append(0)

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

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        k = max(k,c+1)
        c += 1
        queue.append(adj)
print(k)

for e in edge:
    print(color[e[1]-1]+1)

Solution (Python):
n, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for a, b in zip(*[iter(L)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
k = max(map(len, con))
q = [(0, n)]
label = [-1] * n
label[0] = 0
while q:
	cur, ex = q.pop(0)
	nxtex = label[cur]
	i = int(nxtex==0 or ex==k)
	for nxt in con[cur]:
		if label[nxt] > -1:
			continue
		if i==ex:
			i += 1
		label[nxt] = i
		q.append((nxt, nxtex))
		i += 1
print(k)
for a, b in zip(*[iter(L)] * 2):
	t = label[a - 1] + label[b - 1]
	print(t % k if t > k else t)

Solution (Python):
from collections import deque

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

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[i] = c

print(K)
for a in A:
    print(a)

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)

queue = deque()
queue.append(0)

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

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        k = max(k,c+1)
        c += 1
        queue.append(adj)
print(k)

for e in edge:
    print(color[e[1]-1]+1)

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

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

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

color = max(len(g) for g in G)
print(color)

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

def dfs(v=1, p=0, p_col=-1):
    col = 1

    for side, idx in G[v]:
        if side != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(side, v, col)
            col += 1

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

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

n = int(input())

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


ans = [0]*(n-1)
visited = [False]*n

q = deque([(0,0)])
visited[0] = True

mx = 0
while q:
    key,v = q.popleft()
    i = 1
    for x in edges[v]:
        if not visited[x]:
            if key != i:
                visited[x] = True
                ans[l[(v,x)]]=i
                q.append((i,x))
                mx = max(mx,i)
                i += 1
            else:
                visited[x] = True
                i += 1
                ans[l[(v,x)]]=i
                q.append((i,x))
                mx = max(mx,i)
                i += 1

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

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

tree = [[] for _ in range(N)]
for n, (i, j) in enumerate(X):
    tree[i - 1].append((n, j - 1))

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(max(ans))
print(*ans, sep="\n")

Solution (Python):
from collections import deque

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

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u, i in E[v]:
        E[u].remove((v, i))
        c = next(C)
        Q.append((c, u))
        A[i] = c

print(K)
for a in A:
    print(a)

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

n = int(input())

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

ans = [0]*(n-1)

visited = [-1]*n
q = deque([0])
visited[0] = 0

while q:
    v = q.popleft()
    i = 1
    for x in edges[v]:
        if visited[x] < 0:
            if i == visited[v]:
                i += 1
            visited[x] = i
            ans[l[(v,x)]] = i
            q.append(x)
            i += 1

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

Solution (Python):
from collections import deque

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 = [0] * (N - 1)

Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u in E[v]:
        E[u].remove(v)
        c = next(C)
        Q.append((c, u))
        A[memo[(v, u)]] = c

print(K)
for a in A:
    print(a)

Solution (Python):
from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  color[(a, b)] = 0
for a in range(N):
  c_p = color_parents[a]
  c = 1
  for b in tree[a]:
    if c == c_p:
      c += 1
    color[(a, b)] = c
    color_parents[b] = c
    c += 1
print(max(color.values()))
for k in color.keys():
  print(color[k])

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

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    if a >= len(nodes):
        exit()
    if b >= len(nodes):
        exit()
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
if nodes is None:
    exit()

for i, links in enumerate(nodes):
    if links is None:
        exit()
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, edge, queue):
    while len(queue) > 0:
        ni, pc = queue.pop(0)
        links = nodes[ni]

        c = 1
        if pc == c:
            c += 1

        if links is None:
            exit()

        next_links = []
        for n, i in links:
            if n < 0 or i < 0:
                exit()
            if n >= len(nodes) or i >= len(edge):
                exit()

            if edge[i] != 0:
                continue
            edge[i] = c
            queue.append((n, c))

            c += 1
            if pc == c:
                c += 1

queue = [(max_i, 0)]    
fill(nodes, edge, queue)

print(max_l)
for e in edge:
    print(e)

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
d=[]
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
    d+=(a-1,b-1),
s=[(0,0)]
f=[1]+[0]*n
dic=dict()
while s:
    v,color=s.pop()
    i=0
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        i+=1
        if i==color:i+=1
        s+=(w,i),
        dic[v,w]=i
ans=[]
for a,b in d:
    if (a,b)in dic:
        ans+=dic[a,b],
    else:
        ans+=dic[b,a],
print(max(ans))
for t in ans:print(t)

Solution (Python):
from collections import deque
def bfs(succs, preds, start):
    saisyoku = {}
    queue = deque([start])
    used = 0
    while queue:
        v = queue.popleft()
        for u in preds[v]:
            used = saisyoku[preds[v][u]]
        c = 1
        for w in succs[v]:
            if used and c == used:
                c += 1
            saisyoku[succs[v][w]] = c
            queue.append(w)
            c += 1
    return saisyoku
  
n = int(input())
vertices = range(1, n+1)
edges = [list(map(int, input().split())) for _ in range(n-1)]
jisu = {v: 0 for v in vertices}
succs = {v: {} for v in vertices}
preds = {v: {} for v in vertices}
for i, (u, v) in enumerate(edges):
  succs[u][v] = i
  preds[v][u] = i
  jisu[u] += 1
  jisu[v] += 1
colors = max(jisu.values())
print(colors)
saisyoku = bfs(succs, preds, 1)
for _, c in sorted(saisyoku.items()):
    print(c)

Solution (Python):
from collections import deque
N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    
    tree[a-1].append((b-1,i))
    tree[b-1].append((a-1,i))
ans = [0]*N 
q = deque()
q.append((0,0))
ma = 0  
while q:    
    ape1, color1 = q.popleft()    
    color2 = 1
    for ape2, h in tree[ape1]:  
        if ans[h] != 0: 
            continue
        if color1 == color2:    
            color2 += 1
        ans[h] = color2
        q.append((ape2,color2))
        ma = max(ma,color2)
        color2 += 1
print(ma)
for i in range(N-1):
    print(ans[i])

Solution (Python):
import sys

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
ansdict = {}
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			ansdict[(i,j)] = kk 
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(ansdict[(ai-1,bi-1)])

Solution (Python):
from collections import Counter, defaultdict
from queue import Queue
G = defaultdict(list)

C = Counter()
N = int(input())
ans = {}
o = []
for i in range(N-1):
    a, b = map(int, input().split())
    C[a] += 1
    C[b] += 1
    G[a].append(b)
    G[b].append(a)
    ans[(a, b)] = 0
    o.append((a,b))

cs = [0] * (N+1)
def bfs(v):
    ret = 0
    visited = set()
    q = Queue()
    visited.add(v)
    q.put(v)
    while not q.empty():
        v = q.get()
        counter = 1
        for c in G[v]:
            if not c in visited:
                visited.add(c)
                if counter == cs[v]:
                    counter += 1
                cs[c] = ans[(c,v)] = ans[(v,c)] = counter
                counter += 1
                q.put(c)

bfs(1)
print(C.most_common(1)[0][1])
for a,b in o:
    print(ans[(a,b)])

Solution (Python):

import sys
from collections import deque

N=input()

al=[ [] for i in range(N+1) ]
Q=[]    
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
    Q.append((a,b))

K=0
start=None
for i,t in enumerate(al):
    K=max(K,len(t))
    if start is None and len(t)==1:
        start=i

edge={} 


Visit=[ 0 for _ in range(N+1) ] 
q=deque()
q.append(start)
Visit[start]=1
used=[ None for _ in range(N+1) ] 

while q:
    fro=q.popleft()
    for color in range(1,K+1):  
        if used[fro]!=color:
            break

    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	
            q.append(to)
            edge[(fro,to)]=color
            edge[(to,fro)]=color
            used[to]=color
            color+=1
            if used[fro]==color:    
                color+=1

print K
for a,b in Q:
    print edge[(a,b)]

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(100000)
i8 = np.int64
i4 = np.int32


def solve(i, prev, prevc, t, d, ans):
    num = len(t[i])
    x = 1
    if prevc == 1:
        x = 2
    for c in t[i]:
        if c == prev:
            continue
        ans[d[(i, c)]] = x
        num = max(num, solve(c, i, x, t, d, ans))
        x += 1
        if x == prevc:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = {}
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
        d[(a - 1, b - 1)] = count
        d[(b - 1, a - 1)] = count
        count += 1
    num = solve(0, -1, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)

main()

Solution (Python):
N = int(input())
tree = {}
ans = [0 for _ in range(N - 1)]

for i in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    tree.setdefault(a, []).append(i)
    tree.setdefault(b, []).append(i)
for k, v in tree.items():
    a = set(range(1, len(v)+1))
    b = set([ans[i] for i in v])
    if 0 in b:
        b.remove(0)
    a = list(a - b)
    c = 0
    for i in v:
        if ans[i] == 0:
            ans[i] = a[c]
            c += 1
print(max(ans))
print(*ans, sep='\n')

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

import sys
from collections import deque

N=input()

al=[ [] for i in range(N+1) ]
Q=[]    
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
    Q.append((a,b))

K=0
start=None
for i,t in enumerate(al):
    K=max(K,len(t))
    if start is None and len(t)==1:
        start=i

edge={} 


Visit=[ 0 for _ in range(N+1) ] 
q=deque()
q.append(start)
Visit[start]=1
used=[ None for _ in range(N+1) ] 

while q:
    fro=q.popleft()
    for color in range(1,K+1):
        if used[fro]!=color:
            break

    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	
            q.append(to)
            edge[(fro,to)]=color
            edge[(to,fro)]=color
            used[to]=color
            color+=1
            if used[fro]==color:
                color+=1

print K
for a,b in Q:
    print edge[(a,b)]

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

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

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

K = max(len(S) for S in ad)
d = dict()

def dfs(v=0, pv=-1, memo=-1):
    color = 0
    for nv in ad[v]:
        if nv == pv:
            continue
        if color == memo:
            color += 1
        d[(v, nv)] = color
        d[(nv, v)] = color
        dfs(nv, v, color)
        color += 1

dfs()

print(K)
for e in edge:
    print(d[e]+1)

Solution (Python):
from collections import deque

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
q = deque([(-1, 1)])
visited = {i: False for i in range(1, N+1)}
while q:
    p, v = q.popleft()
    visited[v] = True
    if p == -1:
        used = -1
    else:
        used = edge_color[edge_idx[(p, v)]] if p < v else edge_color[edge_idx[(v, p)]]
    c = 1
    for u in E[v]:
        if visited[u]: continue
        q.append((v, u))
        if c == used: c += 1
        if u < v:
            edge_color[edge_idx[(u, v)]] = c
        else:
            edge_color[edge_idx[(v, u)]] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)
 
 
def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color
 
    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color
 
 
print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])

Solution (Python):
N = int(input())
edges = [[] for i in range(N)]
ans = [-1] * (N - 1)
lines = []

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

q = [(0, 0,)]
max_color = 0
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for nv, i in edges[v]:
        ans[i] = color
        q.append((nv, color,))
        color += 1
        if c == color:
            color += 1

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

Solution (Python):
from collections import deque

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

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

	root = 1
	parent = [0] * (N + 1)
	order = []
	stack = [root]
	
	while stack:
		x = stack.pop()
		order.append(x)
		for y in graph[x]:
			if parent[x] == y:
				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 parent[x] == y:
				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

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K

queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(Kpre[bi-1])