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


def solve(n, a_list, b_list):

    
    g = {i: dict() for i in range(n)}
    for i in range(n - 1):
        a, b = a_list[i] - 1, b_list[i] - 1
        g[a][b] = -1
        g[b][a] = -1

    k = max([len(g[a]) for a in range(n)])

    used_color = [-1] * n
    used_color[0] = k - 1
    
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        c = used_color[p]
        for q in g[p].keys():
            if used_color[q] != -1:
                continue
            c += 1
            c %= k
            
            g[p][q] = c
            g[q][p] = c
            used_color[q] = c
            queue.append(q)

    res_list = [0] * (n - 1)
    for i in range(n - 1):
        res_list[i] = g[a_list[i] - 1][b_list[i] - 1] + 1

    return k, res_list


def main():
    n = int(input())
    a_list = [0] * (n - 1)
    b_list = [0] * (n - 1)
    for i in range(n - 1):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b

    k, res_list = solve(n, a_list, b_list)
    print(k)
    for i in range(n - 1):
        print(res_list[i])


def test():
    print(solve(3, [1, 2], [2, 3]))
    print(solve(8, [1, 2, 2, 2, 4, 5, 6], [2, 3, 4, 5, 7, 6, 8]))


if __name__ == "__main__":
    
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
 
N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]

V = [set() for _ in range(N+1)]
for a,b in E:
    V[a].add(b)
    V[b].add(a)

maxc = 0
for v in V:
    maxc = max(maxc,len(v))

CE = {}
for e in E:
    CE[e] = 0

 
def dfs(u,t,c):
    if t > 0:
        CE[(min(u,t),max(u,t))] = c
    cc = c+1
    if cc > maxc:
        cc = 1
    for v in V[u]:
        if CE[(min(u,v),max(u,v))] == 0:
            dfs(v,u,cc)
            cc += 1
            if cc > maxc:
                cc = 1
dfs(1,0,1)
print(maxc)
for e in E:
    print(CE[e])

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
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()
    from collections import defaultdict
    num_c = defaultdict(int)
    E = defaultdict(lambda:defaultdict(int))
    inputE = []
    for i in range(N-1):
        ai,bi = LMIIS()
        if bi < ai:
            ai,bi = bi,ai
        num_c[ai] += 1
        num_c[bi] += 1
        E[ai][bi]= -1
        inputE.append((ai,bi))
    max_c = max(num_c.values())
    


    def colour(e1,c):
        tmpc = 0
        for e2 in E[e1].keys():
            tmpc += 1
            if tmpc == c:
                tmpc += 1
            E[e1][e2] = tmpc
            colour(e2,tmpc)

            
        pass
    
    colour(1,0)
    
    print(max_c)


    for ai,bi in inputE:
        if E[ai][bi] != -1:
            print(E[ai][bi])



if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))



stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)

Solution (Python):
from operator import mul
from functools import reduce



















import sys

sys.setrecursionlimit(10**6)


def inpl():
    return list(map(int, input().split()))



def cmb(n, r):
    
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def gcd(a, b):
    
    while b > 0:
        a, b = b, a % b

    return a


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


def dfs(visit, a, v_b, v_color):
    visit[a] = True

    
    
    
    flag = True
    i = 0
    for b in tmp_list[a]:
        if b == v_b:
            continue
        
        
        
        if flag is True and i >= v_color:
            flag = False
            i += 1
        c = i
        ans_c[min(a, b), max(a, b)] = c
        dfs(visit, b, a, c)
        i += 1

    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

ans_c = {}
tmp_list = [[] for i in range(N + 1)]
for a, b in AB:
    tmp_list[a].append(b)
    tmp_list[b].append(a)

ans = max(len(a) for a in tmp_list)


visit = [False for i in range(N + 1)]
dfs(visit, 1, N + 1, ans + 1)

print(ans)
for a, b in AB:
    print(ans_c[a, b] + 1)

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

def dfs(s, targets):
    global K
    visited[s] = True
    
    for t in targets:
        if visited[t]:
            continue
        mab = max(G3[s], G3[t])
        while (mab in G2[s]) or (mab in G2[t]):
            mab += 1
        K = max(K, mab)
        ans[p2i[(s, t)]]= mab
        G2[s].add(mab)
        G2[t].add(mab)
        while G3[s] in G2[s]:
            G3[s] += 1
        while G3[t] in G2[t]:
            G3[t] += 1
        dfs(t, G[t])

K = 0
N = int(input())
G = [[] for i in range(N+1)]
G2 = [set() for i in range(N+1)]
p2i = {}
visited = [False for i in range(N+1)]
ans = [0 for i in range(N-1)]
G3 = [1] * (N+1)
for i in range(N-1):
    a, b = map(int, input().split())
    p2i[(a, b)] = i
    p2i[(b, a)] = i
    G[a].append(b)
    G[b].append(a)

s = 1
targets = G[s]
dfs(s, targets)
print(K)
for a in ans:
    print(a)

Solution (Python):
from collections import deque

n = int(input())

g = {i: dict() for i in range(n)}

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

k = max([len(g[a]) for a in range(n)])

used_color = [-1] * n
used_color[0] = k - 1

queue = deque([0])
while len(queue) > 0:
    p = queue.popleft()
    c = used_color[p]
    for q in g[p].keys():
        if used_color[q] != -1:
            continue
        c += 1
        c %= k
        
        g[p][q] = c
        g[q][p] = c
        used_color[q] = c
        queue.append(q)

print(k)
for i in range(n - 1):
    print(g[a_list[i]][b_list[i]] + 1)

Solution (Python):
import numpy as np
from collections import deque

N = int(input())


branched = np.zeros((N,2), dtype="int")

branch_add = np.zeros(N, dtype="int")

ans = np.zeros(N - 1)


appeard = np.zeros(N, dtype="int")


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

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    branched[i, 0] = a
    branched[i, 1] = b
    branch_add[i] = a + b
    appeard[a] += 1
    appeard[b] += 1
    
    branch_list[a].append(i)
    branch_list[b].append(i)

color_num = np.max(appeard)

start_node = (np.where(appeard == color_num)[0])[0]


color_queue = deque()

for c, i in enumerate(branch_list[start_node]):
    color_queue.append([branch_add[i] - start_node, i, c])
    ans[i] = c

while len(color_queue) > 0:
    next_queue = color_queue.popleft()
    node = next_queue[0]
    colored_branch = next_queue[1]
    color = next_queue[2]
    color_index = 0
    for i in branch_list[node]:
        if i == colored_branch:
            continue
        
        if color_index == color:
            color_index += 1
        color_queue.append([branch_add[i] - node, i, color_index])
        ans[i] = color_index
        color_index += 1

print(color_num)

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

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

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

V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)

maxc = 0
for v in V:
  maxc = max(maxc,len(v))

CE = {}
for e in E:
  CE[e] = 0


def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = c+1
  if cc > maxc:
    cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,cc)
      cc += 1
      if cc > maxc:
        cc = 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Solution (Python):
def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


if __name__ == '__main__':
    main()

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


ans = max(can)
now = [0]
clr = [0 for _ in range(n)]
ok = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
clr[0] = ans
ok[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y] == 0:
        now.append(y)
        clr[y] = ok[x]
        rank[y] = rank[x] + 1
        ok[x] = ok[x] % ans + 1
        ok[y] = clr[y] % ans + 1
print(ans)

for w in rec:
  a,b = w
  if rank[a] > rank[b]:
    m = a
  else:
    m = b
  print(clr[m])

Solution (Python):
N = int(input())
E = sorted([list(map(int, input().split())) + [i] for i in range(N-1)], key = lambda x:x[1])
E.sort()
ans = [0 for _ in range(N-1)]
flg = [0 for _ in range(N+1)]

t = 0
cnt = 0
ans_a = 0
for i in range(N-1):
	a,b,ind = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans[ind] = cnt
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1



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

Solution (Python):
import sys

sys.setrecursionlimit(100000)

n=int(input())

ans={}
inp_list=[]
G=[0 for i in range(n+1)]
T=[[] for i in range(n+1)]
for i in range(n-1):
    
    a,b=map(int,input().split())
    inp_list.append((a,b))
    T[a].append(b)
    T[b].append(a)

L=[len(ppp) for ppp in T]
mod=max(L)

def addd(x,mod):
    x+=1
    if x==mod+1:
        x=1
    return x

def tansa(now,color):
    
    now_col=color
    for i in T[now]:
        if G[i]==0:
            if now_col==color:
                now_col=addd(now_col,mod)
            G[i]==now_col
            ans[(now,i)]=now_col
            T[i].remove(now)
            tansa(i,now_col)
            now_col=addd(now_col,mod)


tansa(1,0)

print(mod)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append([i, b - 1])
    t[b - 1].append([i, a - 1])
    e.append([a - 1, b - 1])
colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

res = [0 for _ in range(n - 1)]
f = [False for _ in range(n)]


def dfs2(d, c):
    f[d] = True
    nc = 1
    for j in range(len(t[d])):
        if not f[t[d][j][1]]:
            if c == nc:
                nc += 1
            res[t[d][j][0]] = nc
            dfs2(t[d][j][1], nc)
            nc += 1


dfs2(0, 1000000)

print("\n".join(map(str, res)))

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

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


num_children = -1


def dfs(graph, cur, parent, num_children):
    if 0 == len(graph[cur]):
        return num_children
    num_edges = len(graph[cur])
    if not (None == parent):
        num_edges += 1
    num_children = max(num_children, num_edges)
    for child in graph[cur]:
        num_children = dfs(graph, child[0], cur, num_children)
    return num_children


def dfs_color(graph, cur, parent_edge_color, num_colors):
    color = 0
    for child in graph[cur]:
        if parent_edge_color == color:
            color += 1
        colors[child[1]] = color+1
        dfs_color(graph, child[0], color, num_colors)
        color += 1


num_children = dfs(graph, 0, None, num_children)
dfs_color(graph, 0, -1, num_children)
print(num_children)
for color in colors:
    print(color)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

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

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


if __name__ == "__main__":
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

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

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


if __name__ == "__main__":
	main()

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])
color_v = [set() for _ in range(N + 1)]

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number in color_v[V]:
            number += 1
        color[v] = number
        color_v[V].add(number)
        color_v[v].add(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)
input = sys.stdin.readline

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.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, NG = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == NG:
            c += 1
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
li=[0]*(n+1)
for i in range(n-1):
    ab[i].append(i)
ab.sort()
for i in range(n-1):
    li[ab[i][0]]+=1
    li[ab[i][1]]+=1
print(max(li))
ma=max(li)
li2=[1]*(n+1)
ans=[]
for i in range(n-1):
    iro=li2[ab[i][0]]
    ans.append([ab[i][2],iro])
    
    if iro+1>ma:
        iro=0
    li2[ab[i][0]]=iro+1
    li2[ab[i][1]]=iro+1
ans.sort()
for i in range(n-1):
    print(ans[i][1])

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

k = 0
for i in range(n+1):
    k = max(k, len(n_list[i]))

c_list = []
for i in range(1, k+1):
    c_list.append(i)

todo = [(1,0,0)]
seen = [1]
while len(todo) != 0:
    p_from, c_from, before = todo.pop()
    i = 0
    for t in n_list[p_from]:
        p, l = t
        if p == before:
            continue
        else:
            while c_list[i] == c_from:
                i += 1
            color = c_list[i]
            i += 1
            todo.append((p,color,p_from))
            l_list[l] = color
            seen.append(p)
        
    

print(k)
for i in l_list:
    print(i)

Solution (Python):
words = lambda t : list(map(t, input().split()))
n = int(input())

vs = [[] for i in range(n)]
for i in range(n-1):
    s,e = words(int)
    vs[s-1].append((e-1,i))

import queue
q = queue.Queue()
q.put(0)
color = [0] * (n-1)
color_par = [0] * (n)
color_par[0] = -1
while not q.empty():
    v = q.get()
    cur_c = 1
    for (c,i) in vs[v]:
        if color_par[v] == cur_c:
            cur_c +=1
        color[i] = cur_c
        color_par[c] = cur_c
        cur_c += 1
        q.put(c)

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

Solution (Python):
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []

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



for i in range(n):
    if i == 0:
        color = len(tree[i])
    else:
        color = max(color, len(tree[i])+1)

upper = [0 for _ in range(n)]

for i in range(n):
    if not tree[i]:
        continue

    top = upper[i]
    tmp = tree[i].copy()
    cnt = 1
    while tmp:
        if cnt == top:
            cnt += 1
        upper[tmp.pop()] = cnt
        cnt += 1

ans = []
for x, y in edge:
    ans.append(upper[y])
print(color)
print(*ans, sep="\n")

Solution (Python):
n = int(input())
colorU = [-1 for _ in range(n)]
colorD = [-1 for _ in range(n)]
colorU[0] = 0

ab = []
ans = [0 for _ in range(n - 1)]
n -= 1
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a, b, i])
ab.sort()
for i in range(n):
    
    a = ab[i][0]
    b = ab[i][1]
    c = ab[i][2]

    a -= 1
    b -= 1
    
    if colorD[a] == -1:
        if colorU[a] == 1:
            thiscolor = 2
        else:
            thiscolor = 1
    else:
        thiscolor = colorD[a] + 1
        if thiscolor == colorU[a]: 
            thiscolor += 1

    colorU[b] = thiscolor
    colorD[a] = thiscolor
    ans[c] = thiscolor
    
    

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)

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

ans={}
def solve(p,c):
    global ans
    cnt=1
    for vtx in edge[p]:
        while c==cnt:
            cnt+=1
        ans[(p,vtx)]=cnt
        solve(vtx,cnt)
        cnt+=1

solve(0,0)
print(max(ans.values()))
for e in ab:
    print(ans[e])

Solution (Python):
from bisect import bisect_left,insort
n=int(input())
ab=[]
data=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab.append([a,b,i])
    data[a].append(b)
    data[b].append(a)
ans=[0]*(n-1)
ab.sort()
flag=[-1 for i in range(n+1)]
flag[1]=0
que=[1]
while que:
    h=que.pop()
    k=1
    if flag[h]==k:
        k+=1
    for u in data[h]:
        if flag[u]==-1:
            flag[u]=k
            if h>u:
                h,u=u,h
            ans[ab[bisect_left(ab,[h,u])][2]]=k
            que.append(u)
            k+=1
            if flag[h]==k:
                k+=1
print(max(ans))
for i in range(n-1):
    print(ans[i])

Solution (Python):

from collections import deque
n = int(raw_input())
edges = []
for i in range(n-1):
    edges.append(map(int, raw_input().split()))

edge_to_i = {}
graph = [[] for _ in range(n+1)]
ans = [0] * (n-1)

for i in range(len(edges)):
    s,e = edges[i]
    graph[s].append(e)
    graph[e].append(s)
    edge_to_i[(s, e)] = i
    edge_to_i[(e, s)] = i

visited = set([])
q = deque([1])
while q:
    node = q.popleft()
    visited.add(node)

    not_colored = []
    colors = set([])
    for next_node in graph[node]:
        i = edge_to_i[(next_node, node)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not next_node in visited:
            q.append(next_node)

    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1

print len(set(ans))
for i in ans:
    print i

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

N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))


ans = max(count)
c = 1



def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i in pr:
            continue
        if c == col:
            c+=1
        x, y = sorted([i, idx])
        color[(x, y)] = c
        dfs(i, (x, y))
        c+=1

color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Solution (Python):
from collections import defaultdict, deque

nVertices = int(input())
g = [[] for _ in range(nVertices + 1)]
edges = []
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges.append((u, v))
    g[u].append(v)
    g[v].append(u)

colours = defaultdict(int)
q = deque([(0, 1)])
maxColour = 0
while q:
    par, vertex = q.pop()
    parColor = colours[(par, vertex)]
    colour = 1
    for child in g[vertex]:
        if child != par:
            if colour == parColor:
                colour += 1
            colours[(vertex, child)] = colour
            maxColour = max(maxColour, colour)
            colour += 1
            q.appendleft((vertex, child))

print(maxColour)
for e in edges:
    print(colours[e] or colours[e[::-1]])

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

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

hen=[[] for _ in range(N)]
for i in range(N-1):
  a,b=AB[i]
  hen[a-1].append(b)

ans={}
def dfs(l,p):
  col=0
  for i in hen[p-1]:
    col+=1
    if col==l:
      col+=1
    ans[str(p)+","+str(i)]=col
    dfs(col,i)

dfs(-1,1)
print(max(ans.values()))

for a,b in AB:
  print(ans[str(a)+","+str(b)])

Solution (Python):
import sys
import math

def func(s):
    return int(s)-1


N=int(input())
e=[list(map(func,input().split()))+[i] for i in range(N-1)]
e.sort()

x=[0 for i in range(N)]
for i in range(N-1):
    x[e[i][0]]+=1
    x[e[i][1]]+=1
print(max(x))

e2=[[0 for j in range(x[i])]for i in range(N)]
ans=[0 for i in range(N-1)]

y=[0 for i in range(N)]

for i in range(N-1):
    [p,q,r]=e[i]

    e2[p][y[p]]=1
    if y[p]<x[q]: e2[q][y[p]]=1
    ans[r]=y[p]

    for j in range(y[p],x[p]):
        if e2[p][j]==0:
            y[p]=j
            break
    for j in range(y[q],x[q]):
        if e2[q][j]==0:
            y[q]=j
            break

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

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

n = int(input())
edge = {}
tree = [[] for i in range(n)]
color = [0] * (n - 1)
color_par = [-1] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    edge[(a, b)] = i

for i in range(n):
    c = 1
    for v_child in tree[i]:
        if c == color_par[i]:
            c += 1
        color[edge[(i, v_child)]] = c
        color_par[v_child] = c
        c += 1

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

Solution (Python):
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(input())
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 1
q = [(0, None)]
while q:
    u, color = q.pop()
    if color == 1:
        c = 2
    else:
        c = 1
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))
            K = max(K, c)
            c += 1
            if c == color:
                c += 1
                

print(K)
for pair in edge:
    print(color_dict[pair])

Solution (Python):

def solve():
    N =  int(input())
    E = [[] for _ in range(N+1)]
    D = {}
    L = [-1 for _ in range(N)]
    for i in range(1,N):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
        D[(a,b)] = i
    r = 1
    q = [(r,0)]
    d = 0
    while q:
        v, c = q.pop()
        d = max(d, len(E[v]))
        C = 0
        for u in E[v]:
            if L[D.get((v,u), D.get((u,v),-1))] == -1:
                C += 1
                x = C
                if c == x:
                    C += 1
                    x = C
                q.append((u,x))
                L[D.get((v,u), D.get((u,v),-1))] = x
    L[0] = d
    res = '\n'.join(map(str, L))
    return str(res)

if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n=int(input())
ab=[]
root=[[] for i in range(n)] 
for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append((i,b-1))
    root[b-1].append((i,a-1))
c=0
for i in range(n):
    c=max(c,len(root[i]))
print(c)
color=[0]*(n-1)

def dfs(node,par,c):
    if c!=1:
        i=1
    else:
        i=2
    for idx,x in root[node]:
        if x==par:
            continue
        if color[idx]==0:
            color[idx]=i
            dfs(x,node,i)
            i+=1
            if i==c:
                i+=1
dfs(0,-1,0)
for i in range(n-1):
    print(color[i])

Solution (Python):
from collections import defaultdict, deque

nVertices = int(input())
g = [[] for _ in range(nVertices + 1)]
edges = []
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges.append((u, v))
    g[u].append(v)
    g[v].append(u)

colours = defaultdict(int)
q = deque()
colour = 1
maxColour = colour
par = 1
for child in g[par]:
    if child != par:
        colours[(par, child)] = colour
        maxColour = max(maxColour, colour)
        colour += 1
        q.appendleft((par, child))
while q:
    par, vertex = q.pop()
    parColor = colours[(par, vertex)]
    colour = 1
    for child in g[vertex]:
        if child != par:
            if colour == parColor:
                colour += 1
            colours[(vertex, child)] = colour
            maxColour = max(maxColour, colour)
            colour += 1
            q.appendleft((vertex, child))

print(maxColour)
for e in edges:
    print(colours[e] or colours[e[::-1]])