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 deque
n = int(input())
matrix= []
lis = [[] for i in range(n)]
ans = {}
for i in range(n):
    ans[i] = {}
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print(ans[root[0]][root[1]])

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

settansaku = set([])
setmada = {0}
listmada = [(0, None)]  
kouho = 1
num = [0 for _ in range(n-1)]

while kouho != 0:
	for i, cnt in listmada[:]:
		colors = {cnt}
		settansaku.add(i)
		setmada.remove(i)
		listmada.remove((i, cnt))
		kouho -= 1
		c = 0
		for k, j in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					while True:
						if c not in colors:
							listmada.append((k, c))
							colors.add(c)
							num[j] = c
							break
						c += 1
					kouho += 1

print(max(num)+1)
print("\n".join([str(i+1) for i in num]))

Solution (Python):
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
edges = []
for _ in range(n - 1):
	u,v = map(int, raw_input().split(' '))
	edges.append((u,v))
	adj[u].append(v)
	adj[v].append(u)
root = 1
q = collections.deque([root])
h = {}
while(q):
	u = q.popleft()
	c = 1

	used = set([h[tuple(sorted([u,v]))] for v in adj[u] if tuple(sorted([u,v])) in h]) 

	for v in adj[u]:
		t = tuple(sorted([u,v])) 
		if t not in h:
			while(c in used): c+=1
			h[t] = c	
			c+=1
			q.append(v)
print max(h.values())
for u,v in edges:
	print h[(u,v)]

Solution (Python):
import collections

n = int(input())
graph = [tuple(map(int, input().split())) for _ in range(n - 1)]
tree = [[] for _ in range(n)]
deg = [0] * n
color = {}
for a, b in graph:
    a, b = min(a - 1, b - 1), max(a - 1, b - 1)
    deg[a] += 1
    deg[b] += 1
    tree[a].append(b)
    tree[b].append(a)
    color[(a, b)] = 0
color_max = max(deg)
print(color_max)

c = [0] * n
c[0] = -1
que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    tmp = 1
    for j in tree[i]:
        if c[j] != 0: continue
        a, b = min(i, j), max(i, j)
        if tmp == c[i]: tmp += 1
        color[(a, b)] = tmp
        c[j] = tmp
        que.append(j)
        tmp += 1

for a, b in graph:
    a, b = min(a - 1, b - 1), max(a - 1, b - 1)
    print(color[(a, b)])

Solution (Python):
n = int(input())
L = []
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    L.append((a, b))
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
k = 0
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
key = sorted(d.keys())
dd = {1: 0}
ans = {}
for i in key:
    v = d[i]
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        ans[(i, j)] = c
        dd[j] = c
for a, b in L:
    print(ans[(a, b)])

Solution (Python):
from collections import deque

N = int(input())


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

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


que = deque([])
que.append((0, 0))

while que:
    v, pc = que.popleft()
    c = 1
    for nv, i in tree[v]:
        
        if path[i] == 0:
            c = c+1 if c == pc else c
            path[i] = c
            que.append((nv, c))
            c += 1
    
    
print(max(path))
print(*path, sep="\n")

Solution (Python):
import sys
from collections import deque


N = int(input())
edge = [[] for _ in range(N)]
for i, s in enumerate(sys.stdin.readlines()):
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append((b, i))
    edge[b].append((a, i))


path = [None] * (N - 1)
q = deque()
q.append((0, 0))

while q:
    v, pc = q.popleft()
    c = 1
    for nv, i in edge[v]:
        if path[i] is None:
            c = c + 1 if c == pc else c
            path[i] = c
            q.append((nv, c))
            c += 1

print(max(path))
print(*path, sep='\n')

Solution (Python):
from collections import deque
n = int(input())
edges=[[]for i in range(n)]
nodes=[None]*n
for i in range(1,n):
    a , b = map(int, input().split())
    edges[a-1].append(i)
    edges[b-1].append(i)
    nodes[i]=(a-1,b-1)
ma =0
for i in range(n):
    ma=max(ma,len(edges[i]))

col=[None]*n
d = deque([(0,0)])
while d:
    t=1
    v , ex_col = d.pop()
    for i in edges[v]:
        if col[i] is None:
            if t==ex_col:
                t+=1
            col[i]=t
            a1,b1=nodes[i]
            if a1==v:
                d.append((b1,t))
            else:
                d.append((a1,t))
            t+=1

print(ma)
for i in range(1,n):
    print(col[i])

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

n = int(input())
tree = [[] for _ in range(n)]
dic = {}

for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    dic[(a - 1, b - 1)] = i
ans = [0 for _ in range(n - 1)]
max_color = 0

def dfs(pos, before_pos, before_color):
    global max_color
    color = 1
    for next_pos in tree[pos]:
        if color == before_color:
            color += 1
        if next_pos == before_pos:
            continue
        before = min(pos, next_pos)
        after = max(pos, next_pos)
        ans_ind = dic[(before, after)]
        if pos < next_pos:
            ans[ans_ind] = color
        else:
            ans[ans_ind] = color
        max_color = max(color, max_color)
        dfs(next_pos, pos, color)
        color += 1
dfs(0, -1, -1)

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

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

numOfColors = 0
edges = [[] for j in range(n+1)]
ngColor = [-1]*(n+1)
outsI = [[] for j in range(n+1)]
outs = [0]*(n-1)

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

numOfColors = len(edges[1])
for i in range(2, len(edges)):
  numOfColors = max(len(edges[i])+1, numOfColors)




for i in range(len(edges[1])):
  ngColor[edges[1][i]] = i+1
  outs[outsI[1][i]] = i+1
  
queue = []
queue.extend(edges[1])
while queue != []:
  v = queue.pop(0)
  c = 0
  for i in range(len(edges[v])):
    c += 1
    if c == ngColor[v]:
      c += 1
    ngColor[edges[v][i]] = c
    outs[outsI[v][i]] = c
  queue.extend(edges[v])

print(numOfColors)
for out in outs:
  print(out)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]

    node_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        node_data[a].add(b)
        node_data[b].add(a)

    ans_num = 0
    for i in range(1, num + 1):
        ans_num = max(ans_num, len(node_data[i]))

    edge_data = defaultdict(int)
    ans_count = 0

    for i in range(1, num + 1):
        now_list = list(node_data[i])
        now_list.sort()
        count = bisect.bisect_left(now_list, i) + 1

        use_set = set()
        for ele in now_list[:count - 1]:
            use_set.add(edge_data[(i, ele)])
        now_indx = 1

        for ele in now_list[count - 1:]:
            while now_indx in use_set:
                now_indx += 1

            edge_data[(i, ele)] = now_indx
            edge_data[(ele, i)] = now_indx
            use_set.add(now_indx)

        ans_count = max(ans_count, now_indx)

    print(ans_count)
    for i in range(num - 1):
        a, b = data[i]
        ans = edge_data[(a, b)]
        print(ans)








if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
adj = [[] for _ in range(N)]
degrees = [0 for _ in range(N)]
edges = {}
for i in range(N - 1):
    a, b = map(int, input().split()) 
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    degrees[a] += 1
    degrees[b] += 1
    edges[(a, b)] = i

max_degree = max(degrees)
print(max_degree)

edge_colors = [-1 for _ in range(N - 1)]
visited = [False for _ in range(N)]

def dfs(v, color):
    global max_degree
    if visited[v]:
        return
    visited[v] = True

    next_color = color + 1
    next_color %= max_degree
    for u in adj[v]:
        if visited[u]:
            continue
        if u < v:
            edge_colors[edges[(u, v)]] = next_color
        else:
            edge_colors[edges[(v, u)]] = next_color

        dfs(u, next_color)
        next_color += 1
        
        next_color %= max_degree

dfs(0, -1)
for i in range(N - 1):
    print(edge_colors[i] + 1)

Solution (Python):
from collections import deque

n = int(input())
rg = [[] for _ in range(n)]
ret_dict = dict()
ls = []

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


deq = deque()
deq.append((0, 0))

visited = set()
visited.add(0)

ret = 0

while deq:
    head, color = deq.pop()
    n_color = 1
    for item in rg[head]:
        if item not in visited:
            visited.add(item)
            if n_color == color:
                n_color += 1
            ret = max(ret, n_color)
            deq.append((item, n_color))
            ret_dict[(min(head, item), max(head, item))] = n_color
            n_color += 1


print(ret)
for item in ls:
    print(ret_dict[item])

Solution (Python):
from collections import deque

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

l = [len(i) for i in edge]
k = max(l)
root = l.index(k)

d = deque()
d.append([root, 0])
res = [0] * (n - 1)
while d:
    node, par_color = d.popleft()
    color = 0
    for e, idx in edge[node]:
        if res[idx] > 0:
            continue

        color += 1
        if color == par_color:
            color += 1
        d.append([e, color])
        res[idx] = color

print(k)
for c in res:
    print(c)

Solution (Python):
from queue import Queue
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

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

root = 0
maxdeg = 0
for i in range(1, n + 1):
    if len(adj[i]) > maxdeg:
        maxdeg = len(adj[i])
        root = i

print(str(maxdeg) + '\n')
colors = [i+1 for i in range(maxdeg)]

hashc = {}
q = Queue()
q.put((root, -1, -1))
while not q.empty():
    u, par, col = q.get()
    i = 0
    for child in adj[u]:
        if child == par: continue
        if colors[i] == col: i += 1
        hashc[(u, child)] = colors[i]
        hashc[(child, u)] = colors[i]
        q.put((child, u, colors[i]))
        i += 1

for e in edges:
    print(str(hashc[e]) + '\n')

Solution (Python):
from collections import deque

N = int(input())

int1 = lambda x: int(x) - 1
edges = [[] for _ in range(N)]
nodes = [None] * N
for i in range(1, N):
    a, b = map(int1, input().split())
    edges[a].append(i)
    edges[b].append(i)
    nodes[i] = (a, b)


C = max(len(x) for x in edges)
colors = [None] * N
d = deque([(0, 0)])
while d:
    v, parent_color = d.pop()
    i = 1
    for x in edges[v]:
        if colors[x] is None:
            if i == parent_color:
                i += 1
            colors[x] = i
            a, b = nodes[x]
            d.append((b if a == v else a, i))
            i += 1


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

Solution (Python):

"""
D - Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d

"""
import sys


from collections import OrderedDict, deque

def main(args):
    N = int(input())
    G = [[] for _ in range(N+1)]
    res = OrderedDict()
    for _ in range(N-1):
        a, b = map(int, input().split())
        res[(a, b)] = -1
        G[a].append(b)
        G[b].append(a)

    k = max(len(g) for g in G)
    colors = [0 for _ in range(N+1)]
    q = deque([1])
    visited = set([1])
    while q:
        cn = q.popleft()
        color = 1
        for nn in G[cn]:
            if nn not in visited:
                if color == colors[cn]:
                    color += 1
                visited.add(nn)
                q.append(nn)
                c = color
                colors[nn] = color
                color += 1
                if (cn, nn) in res:
                    res[(cn, nn)] = c
                if (nn, cn) in res:
                    res[(nn, cn)] = c
    print(k)
    for v in res.values():
        print(v)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
from collections import deque

N = int(input())
K = 0
Ans = [0] * (N-1)
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Edge[a].append((b, _))
    Edge[b].append((a, _))

Q = deque()
Q.append((0, 0))
P = [-1] * N
while Q:
    now, color = Q.popleft()
    cnt = 1
    for nex, num in Edge[now]:
        if cnt == color:
            cnt += 1
        if nex == P[now]:
            continue
        if Ans[num] != 0:
            continue
        Q.append((nex, cnt))
        Ans[num] = cnt
        K = max(cnt, K)
        cnt += 1

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

Solution (Python):
from collections import deque
n = int(input())
zyun = []
route = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    zyun.append([a,b])
    route[a].append(b)
iro = [0 for i in range(n+1)]
ans = {}
q = deque()
q.append(1)
while q:
    now = q.popleft()
    cou = 1
    for k in route[now]:
        if iro[now] == cou:
            cou += 1
        ans[str(now) + "+" + str(k)] = cou
        iro[k] = cou
        q.append(k)
        cou += 1
print(max(iro))
for i,j in zyun:
    print(ans[str(i)+"+"+str(j)])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(curr, pare, pare_c, k, color_dic):
    curr_c = pare_c
    for chi in g[curr]:
        if chi == pare: continue
        curr_c = curr_c%k + 1
        color_dic[(curr,chi)] = curr_c
        dfs(chi, curr, curr_c, k, color_dic)


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


k = 0
for node in g:
    k = max(len(node),k)


color_dic = {}
dfs(1, -1, 0, k, color_dic)

print(k)
for edge in gl:
    print(color_dic[edge])

Solution (Python):

from collections import deque

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append((b,i))
        adj[b].append((a,i))
    p = max([len(a) for a in adj])
    ans = [-1] * (N-1)
    visited = [-1] * N
    visited[0] = 0
    q = deque([0])
    
    while q:
        now = q.popleft()
        tmp = 0
        for v in adj[now]:
            if visited[v[0]] == 0:
                tmp = ans[v[1]]
                break
        
        for v in adj[now]:
            if visited[v[0]] < 0:
                q.append(v[0])
                ans[v[1]] = (tmp+1) % p
                tmp += 1
                visited[v[0]] = 0
                if ans[v[1]] == 0:
                    ans[v[1]] += p
    print(p)
    [print(a) for a in ans]

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque, defaultdict
n = int(input())
l = [[] for i in range(n + 1)]
ab = [list(map(int, input().split())) for i in range(n - 1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)
que = deque([1])
p = [-1] * (n + 1)
p[1] = -2
ma = max([len(i) for i in l])
d = defaultdict(int)
print(ma)
while que:
    u = que.popleft()
    x = d[(u, p[u])]
    c = 1
    for v in l[u]:
        if p[v] != -1:
            continue
        p[v] = u
        if c == x:
            c += 1
        d[(u, v)] = d[(v, u)] = c
        c += 1
        que.append(v)
for a, b in ab:
    print(d[(a, b)])

Solution (Python):
n = int(input())
g = [[] for i in range(n+1)]
d = {}
l = [-1] * (n-1)
max_idx = 0
for i in range(n-1):
  u,v = map(int, input().split())
  d[(u,v)] = i
  d[(v,u)] = i
  g[u].append((u,v))
  g[v].append((v,u))
  if len(g[max_idx]) < len(g[u]):
    max_idx = u
  if len(g[max_idx]) < len(g[v]):
    max_idx = v
m = len(g[max_idx])
stack = []
count = m
while len(g[1]) > 0:
  u2, v2 = g[1].pop()
  l[d[(u2, v2)]] = count
  count -= 1
  stack.append((u2, v2))

while len(stack) > 0:
  u, v = stack.pop()
  
  if len(g[v]) > 0:
    count = m
    while len(g[v]) > 0:
      u2, v2 = g[v].pop()
      if count == l[d[(u, v)]]:
        count -= 1
      if l[d[(u2, v2)]] == -1:
        l[d[(u2, v2)]] = count
        count -= 1
        stack.append((u2, v2))
print(m)
for i in range(n-1):
  print(l[i])

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

from collections import defaultdict
g = defaultdict(list)
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

k = 0
for key in g:
    k = max(k, len(g[key]))
print(k)

ans = dict()
q = [(0, -1)] 
visited = set([0])
while q:
    cur, col = q.pop()

    if col == 0:
        tmp = 1
    else:
        tmp = 0

    for target in g[cur]:
        if target not in visited:
            q.append((target, tmp))
            visited.add(target)
            ans[(cur, target)] = tmp

            if tmp + 1 == col:
                tmp += 2
            else:
                tmp += 1

for a, b in ab:
    key = (a-1, b-1)
    print(ans[key] + 1)

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

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

res = [None] * (N-1)
def dfs(n, c=-1, p=-1):
  if c==-1 or c>1: 
    nc = 1
  else:
    nc = c+1
  for nei,i in adj[n]:
    if nei == p: continue
    res[i] = nc
    dfs(nei, nc, n)
    nc += 1
    if nc==c: nc += 1

dfs(0)
print(max(res))
for r in res: print(r)

Solution (Python):
from collections import defaultdict, deque

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

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

col_max = max([len(row) for row in adj])

cols = defaultdict(int)
s = 1
dq = deque([s])
p = [-1] * (n + 1)
p[s] = -2
while dq:
    u = dq.popleft()
    c_banned = cols[(u, p[u])]
    c = 1
    for v in adj[u]:
        if p[v] != -1:
            continue
        p[v] = u
        if c == c_banned:
            c += 1

        cols[(u, v)] = cols[(v, u)] = c
        c += 1

        dq.append(v)

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

Solution (Python):
from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)

Solution (Python):
from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] 
d=[set() for _ in range(N)] 
e=[ False for _ in range(N)] 
f=[0]*N  
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)






v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])

Solution (Python):
n=int(input())
ki=[[] for _ in range(n)]
hen=[tuple(map(int,input().split())) for i in range(n-1)]
color={(hen[i][0]-1,hen[i][1]-1):0 for i in range(n-1)}
for i in range(n-1):
  a,b=hen[i][0],hen[i][1]
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
mcol=0
ne=0
for i in range(n):
  if len(ki[i])>mcol:
    mcol=len(ki[i])
    ne=i
print(mcol)
from collections import deque
d=deque()
d.append(ne)
visited=[False]*n
visited[ne]=True
col=[0]*n
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    if g>i:
      x,y=i,g
    else:
      x,y=g,i
    color[(x,y)]=col[g]%mcol+1
    col[g],col[i]=color[(x,y)],color[(x,y)]
for i in hen:
  print(color[(i[0]-1,i[1]-1)])

Solution (Python):
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N - 1)


def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1


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

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, id): self.to, self.id = to, id

def main():
    N = Z()
    col = [0] * (N-1)
    G = collections.defaultdict(list)
    for i in range(N-1):
        a, b = ZZ()
        G[a].append(edge(b, i))
        G[b].append(edge(a, i))
    numCol = 0
    for i in range(1, N+1): numCol = max(numCol, len(G[i]))

    def dfs(v):
        colSet = set()
        for ed in G[v]:
            if col[ed.id] != 0: colSet.add(col[ed.id])
        c = 1
        for ed in G[v]:
            if col[ed.id] != 0: continue
            while c in colSet: c += 1
            col[ed.id] = c
            c += 1
            dfs(ed.to)

    dfs(1)
    print(numCol)
    for i in range(N-1): print(col[i])

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for i in range(n)]
edge = []

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

ans = []
def color(a, c=-1, fromnode=None):
    i = 0
    cp = 0
    while i < len(tree[a]):
        nxt, idn = tree[a][i]
        if nxt==fromnode:
            i+=1
            continue 
        if cp == c:
            cp+=1
        ans.append([idn, cp])
        color(nxt, cp, a)
        i+=1
        cp+=1

color(0)

ans.sort()
ans = [c+1 for idn, c in ans]
print(max(ans))
for a in ans:
    print(a)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
class Edge:
    def __init__(self, to, id):
        self.to = to
        self.id = id
N = int(input())
graph = {}
ans = [0] * (N-1)
def dfs(v, c=-1, p=-1):
    global graph, ans
    k = 1
    for edge in graph[v]:
        nv = edge.to
        if nv == p:continue
        if k == c:k += 1
        ans[edge.id] = k
        dfs(nv, k, v)
        k += 1
def main():
    global N, graph, ans
    for i in range(N):
        graph[i] = set()
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a-1].add(Edge(b-1, i))
        graph[b-1].add(Edge(a-1, i))
    color_count = 0
    for i in range(N):
        color_count = max(color_count, len(graph[i]))
    dfs(0, 0, -1)
    print(color_count)
    for x in ans:
        print(x)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    
    

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    
    

    
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = dict()
    

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if not ((v1, v2) in vc):
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[(v1, v2)] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[(v1, v2)])


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

N, *ab = map(int, open(0).read().split())
B = ab[1::2]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])

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

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

    def dfs(vNow, vPar, clrPar):
        clr = 1
        for v2, i in adjL[vNow]:
            if v2 == vPar: continue
            if clr == clrPar:
                clr += 1
            anss[i] = clr
            dfs(v2, vNow, clr)
            clr += 1

    anss = [0] * (N-1)
    dfs(0, -1, 0)

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


solve()

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

que=deque([0])
ans=[0]*(n-1)
par=[0]*n
par[0]=-1
while que:
    x=que.popleft()
    p=par[x]
    color=1
    for tup in arr[x]:
        if p==color:
            color+=1
        if ans[tup[1]]==0:
            ans[tup[1]]=color
            par[tup[0]]=color
            color+=1
            que.append(tup[0])
print(max(ans))
print(*ans,sep='\n')

Solution (Python):




import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a-1].append([b-1,i])
  G[b-1].append([a-1,i])
  
ans = [0 for i in range(N - 1)]
from collections import deque

q = deque([[0, 0, -1]])
while q:
  v,pcol,parent = q.popleft()
  cnt = 1
  for child in G[v]:
    if child[0] == parent:
      continue
    if cnt == pcol:
      cnt += 1
    ans[child[1]] = cnt
    q.append([child[0],cnt,v])
    cnt += 1

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

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

nc=0

for i, next in enumerate(nextlist):
    tmp=len(next)
    if tmp>nc:
        nc=tmp
        nci=i+1
print(nc)

linedic={}

seen=set()
todo=[[[nci,0]],[]]
seen.add(nci)

i=0
while todo[i] != []:
    if i ==0:
        x=1
    else:
        x=0
    todo[x]=[]
    
    for to in todo[i]:
        tmp=to[1]
        k=1
        for next in nextlist[to[0]-1]:
            if not next in seen:
                if k == tmp:
                    k +=1
                seen.add(next)
                todo[x].append([next,k])
                linedic[(min(to[0],next),max(to[0],next))]=k
                k += 1
                
    i=x

for ab in ablist:
    print(linedic[ab])

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

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque

def solve():
    N = II()
    E = [[] for _ in range(N)]

    for i in range(N-1):
        a, b = MI1()
        E[a].append((b, i))
        E[b].append((a, i))

    q = deque([(0, -1, -1)])
    ans = [0] * (N-1)
    while len(q) > 0:
        current, v_pre, c_pre = q.popleft()
        color = 1
        for (nv, idx) in E[current]:
            if nv == v_pre: continue
            if color == c_pre:
                color += 1
            q.append((nv, current, color))
            ans[idx] = color
            color += 1

    print(max(ans))
    printlist(ans)

if __name__ == '__main__':
    solve()