Problem:
 Score : 400 points    Problem Statement  Given is a tree G with N vertices.
The vertices are numbered 1 through N , and the i -th edge connects Vertex a_i and Vertex b_i .  Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.  Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.      Constraints   2 \le N \le 10^5  1 \le a_i \lt b_i \le N  All values in input are integers.  The given graph is a tree.         Input  Input is given from Standard Input in the following format:  N  a_1  b_1  a_2  b_2  \vdots  a_{N-1}  b_{N-1}       Output  Print N lines.  The first line should contain K , the number of colors used.  The (i+1) -th line (1 \le i \le N-1) should contain c_i , the integer representing the color of the i -th edge, where 1 \le c_i \le K must hold.  If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.        Sample Input 1 3
1 2
2 3      Sample Output 1 2
1
2       Sample Input 2 8
1 2
2 3
2 4
2 5
4 7
5 6
6 8      Sample Output 2 4
1
2
3
4
1
1
2       Sample Input 3 6
1 2
1 3
1 4
1 5
1 6      Sample Output 3 5
1
2
3
4
5

Solution (Python):

import sys
import queue

def create_graph(N, a, b):
    g = {}
    for i in range(N-1):
        if a[i] in g:
            g[a[i]][b[i]] = 0
        else:
            g[a[i]] = {b[i]: 0}
        if b[i] in g:
            g[b[i]][a[i]] = 0
        else:
            g[b[i]] = {a[i]: 0}
    return g


def bfs(g, s):
    Q = queue.Queue()
    Q.put(s)
    while not Q.empty():
        p = Q.get()
        cs = set(range(len(g[p])+2)) - set([v for k, v in g[p].items()])
        for q in g[p].keys():
            
            if not g[p][q]:
                c = cs.pop()
                g[p][q] = c
                g[q][p] = c
                Q.put(q)


def solve(N: int, a, b):
    g = create_graph(N, a, b)
    bfs(g, a[0])
    
    m = 1
    for i in range(N-1):
        m = max(m, g[a[i]][b[i]])
    print(m)
    for i in range(N-1):
        print(g[a[i]][b[i]])


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys, os
import collections

MOD = 10 ** 9 + 7

class Edge:
  def __init__(self, to, edge_id):
    super().__init__()
    self.to = to
    self.edge_id = edge_id

class DFSState:
  def __init__(self, vertex, parent_color = -1, parent = -1):
    super().__init__()
    self.vertex = vertex
    self.parent_color = parent_color
    self.parent = parent

def solve(input_stream):
  N = read_int(input_stream)
  graph = [[] for i in range(N)]
  answer = [0 for i in range(N - 1)]
  K = 0
  for index in range(N-1):
    i,j = read_ints(input_stream)
    i-=1
    j-=1
    graph[i].append(Edge(j, index))
    graph[j].append(Edge(i, index))
  dfs = [DFSState(0)]
  while len(dfs) > 0 :
    color = 1
    state = dfs.pop(0)
    for index, value in enumerate(graph[state.vertex]):
      to = value.to
      edge_id = value.edge_id
      if to == state.parent:
        continue
      if color == state.parent_color:
        color += 1
      answer[edge_id] = str(color)
      dfs.append(DFSState(to, color, state.vertex))
      color += 1
  for value in graph:
    K = max(K, len(value))
  ans = [str(K)]
  ans.extend(answer)
  return ans

    


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**7)
n = int(input())
edge = [tuple(map(int,input().split()))for _ in range(n - 1)]
T = [[] for _ in range(n)]
for i,(a,b) in enumerate(edge):
  
  T[a -1].append([b - 1,i])
  
ans = [None] * (n - 1)
def rec(cur,color):
  cnt = 1
  for (to,j) in T[cur]:
    if cnt == color:
      cnt += 1
    ans[j] = cnt
    rec(to,cnt)
    cnt += 1
rec(0,0)
print(max(ans))
[print(a) for a in ans]

Solution (Python):
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  val=len(set)+1
  if not(val in set):
    return(val)
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)


ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] 
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) 
  for _to, e_i in edge[vrt]: 
    if _to==_from:
      continue     
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)

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

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

ans = [None]*(N-1)
def rec(cur, color):
    cnt = 1
    for (to, j) in G[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        rec(to, cnt)
        cnt += 1

rec(0,0)
print(max(ans))
[print(a) for a in ans]

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

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

def rec(cur,color):
    count = 1
    for (to,j) in G[cur]:
        if count == color:
            count += 1
        ans[j] = count
        rec(to,count)
        count += 1
rec(0,0)
print(max(ans))
print(*ans,sep="\n")

Solution (Python):
N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]


C = [0]*N

Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        
        
        c += 1 + int(C[q-1] == c+1)
        
        C[w-1] = c
        
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])

Solution (Python):
N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]


C = [0]*N

Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        
        
        c += 1 + int(C[q-1] == c+1)
        
        C[w-1] = c
        
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])

Solution (Python):
from queue import Queue

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

color = [0] * (N-1)
used_color =  [set() for _ in range(N)]

adj = [set() for _ in range(N)]
for i, (a, b) in enumerate(ab):
    adj[a - 1].add((i, b - 1))
    adj[b - 1].add((i, a - 1))

root = max(range(N), key=lambda x: len(adj[x]))

q = [root]

while q:
    node1 = q.pop()
    c=1
    for i, node2 in adj[node1]:
        while c  in used_color[node1]:
            c += 1
        color[i]=c
        used_color[node1].add(c)
        used_color[node2].add(c)
        adj[node2].remove((i, node1))
        q.append(node2)

print(len(used_color[root]))
for c in color:
    print(c)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ki = [[]for j in range(n)]
for i in range(n-1):
	    a,b=map(int,input().split())
	    a-=1
	    b-=1
	    ki[a].append([b,i])
	    ki[b].append([a,i])


a=[0]*n
for i in range(n):
	    a[i]= len(ki[i])
print(max(a))
clist=[-1]*(n-1)
visited=[[0]for i in range(n)]
def dfs(now,last,ban_color=-1):
	    color =1
	    for next,id in ki[now]:
	    	    
                     
	    	    if next == last:continue
	    	    if color == ban_color:
	    	    	    color+=1
	    	    clist[id] = color
	    	    dfs(next,now,color)
	    	    
	    	    color+=1
	    	    
dfs(0,-1)
print(*clist)

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

n = int(input())
T = [[] for _ in range(n)]
ab = [ tuple(map(int, input().split())) for _ in range(n-1) ]
for a, b in ab:
  T[a-1].append(b-1)
  T[b-1].append(a-1)
d = { (min(a)-1, max(a)-1):i for i, a in enumerate(ab) }
A = [1]*(n-1)
M = [set() for _ in range(n)]
seen = [False]*n
seen[0] = True
def dfs(v):
  now = 1
  for nv in T[v]:
    if not seen[nv]:
      seen[nv] = True
      while now in M[v]:
        now += 1
      A[d[(min(v, nv), max(v, nv))]] = now
      M[v].add(now)
      M[nv].add(now)
      dfs(nv)
dfs(0)
print(max(A), *A, sep="\n")

Solution (Python):
N = int(input())
edges = []
node = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges += (a-1, b-1),
  node[a-1] += b-1,
  node[b-1] += a-1,

stuck = [(0,0)]
f = [1]+[0]*N
color_dic = dict()
while stuck:
  v, color = stuck.pop()
  i = 0
  for w in node[v]:
    if f[w]:
      continue
    f[w] = 1
    i += 1
    if i == color:
      i += 1
    stuck += (w,i),
    color_dic[v,w] = i

ans = []
for a,b in edges:
  if (a,b) in color_dic:
    ans += color_dic[a,b],
  else:
    ans += color_dic[b,a],

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

Solution (Python):
N=int(input().strip())
ab=[]
from collections import defaultdict
node=defaultdict(list)
edge={}
ans={}
for i in range(N-1):
    a,b=(map(int, input().strip().split()))
    edge[i]=(a,b)
    node[a].append(b)
    node[b].append(a)
from queue import Queue
q=Queue()
q.put(1)
K=0
col=defaultdict(set)
K=0
while not q.empty():
    i=q.get()
    nxt=[j for j in node[i] if j>i]
    c=1
    for n in nxt:
        while c in col[i]or c in col[n]:
            c+=1
        ans[(i,n)]=c
        col[i].add(c)
        col[n].add(c)
        K=max(K,c)
        q.put(n)
print(K)
for i in range(N-1):
    print(ans[edge[i]])

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])
 
ans = [None] * (N-1)
 
def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])

    link = [set() for _ in range(n+1)]
    edge = []

    for i, ab in enumerate(args[1:]):
        a, b = sorted(map(int, ab.split()))
        edge.append((a, b))
        link[a].add(b)
        link[b].add(a)

    n_color = max(map(len, link))

    color = {}

    queue = [(0, 1)]

    while queue:
        parent, cur = queue.pop()
        used = color[tuple(sorted((parent, cur)))] if 0 < parent else 0
        c = 1

        for child in link[cur]:
            if child == parent:
                continue

            if c == used:
                c += 1
            color[tuple(sorted((cur, child)))] = c
            c += 1

            queue.append((cur, child))

    return str(n_color) + '\n' \
        + '\n'.join(map(str, (color[ab] for ab in edge)))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):


from collections import deque


test = ""

"""
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
"""
test = list(reversed(test.strip().splitlines()))
if test:
    def inp():
        return test.pop()
else:
    def inp():
        return input()
    

n = int(inp())
edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, inp().split()))


adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)


tag_dict = {1: 0}
edge_dict = dict()
nodeQ = deque([1])

while len(nodeQ):
    current_node = nodeQ.popleft()
    tag = tag_dict[current_node]
    
    a_list = [a for a in adjacency_list[current_node] if current_node < a]
    for (i, a) in enumerate(a_list):        
        tag_dict[a] = (tag + i) % (max_order) + 1
        edge_dict[(current_node, a)] = tag_dict[a]
        nodeQ.append(a)
             
print(max_order)
for edge in edges:
    print(edge_dict[edge])

Solution (Python):
import queue

n = int(input())
G = [[] for i in range(n)]
vp = [() for i in range(n - 1)]

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

que = queue.Queue()
que.put(0)
used = [0] * n
used[0] = 1
K = 0
cs = [0] * n
dic = {}
while not que.empty():
        v = que.get()
        if len(G[v]) > K:
                K = len(G[v])
        col = 1
        for u in G[v]:
                if used[u]:
                        continue
                if col == cs[v]:
                        col += 1
                cs[u] = col
                dic[(u, v)] = col
                dic[(v, u)] = col
                col += 1
                used[u] = 1
                que.put(u)
print(K)
for i in vp:
        print(dic[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])

ans = [None] * (N-1)

def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]

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

    graph = [[] for i in range(0, N)]
    edge = [0] * (N - 1)
    for i in range(0, N - 1):
        frm, to = list(map(int, input().split()))
        frm -= 1
        to -= 1
        graph[frm].append(i)
        graph[to].append(i)
    
    maxColor = 0
    for node in graph:
        usedColor = []
        maxColor = max(maxColor, len(node))
        for eNo in node:
            if edge[eNo] is not 0:
                usedColor.append(edge[eNo])
        
        nowColor = 1
        for eNo in node:
            if edge[eNo] is 0:
                while nowColor in usedColor:
                    nowColor += 1

                edge[eNo] = nowColor
                usedColor.append(nowColor)

    print(maxColor)
    
    for color in edge:
        print(color)


def main():
    ABC146D_ColoringEdge()

if __name__ == "__main__":
    main()

Solution (Python):
import sys 
sys.setrecursionlimit(500*500) 

N=int(input().strip())
a=[0]*(N-1) 
b=[0]*(N-1)

ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] 
        self.id=[[] for j in range(N)] 

def dfs(v,p,c_p): 
    lst=data.to[v] 
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) 
    data.to[b].append(a)
    data.id[b].append(i)



dfs(0,-1,-1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque

def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(range(1,k+1))
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

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

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

def main():
	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])

main()

Solution (Python):
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
edges=[tuple(map(int,input().split())) for i in range(n-1)]
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    
    edge_color[(V,I)]=vertex[v]%color+1
    vertex[V],vertex[I]=edge_color[(V,I)],edge_color[(V,I)] 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

Solution (Python):
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
edges=[tuple(map(int,input().split())) for i in range(n-1)]
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
if most_connected>graph[most_connected][0]:
  most_connected,graph[most_connected][0]=graph[most_connected][0],most_connected
edge_color[(most_connected,graph[most_connected][0])]=1
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    
    edge_color[(V,I)]=vertex[v]%color+1
    vertex[V],vertex[I]=edge_color[(V,I)],edge_color[(V,I)] 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

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_num = {}
G = [[] for i in range(n)]
ans = [0] * (n - 1)
for i in range(n - 1):
    s, e = edges[i]
    s = s - 1
    e = e - 1
    edge_num[(s, e)] = i
    edge_num[(e, s)] = i
    G[s].append(e)
    G[e].append(s)
vis = set([])
q = deque([0])
vis.add(0)
while q:
    u = q.popleft()
    not_colored = []
    colors = set([])
    for v in G[u]:
        i = edge_num[(u, v)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not v in vis:
            vis.add(v)
            q.append(v)
    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(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

def dfs(v, c):
    res = -1
    i = 0
    used[v] = 0
    for u in e[v]:
        if used[u] == 1:
            i += 1
            if i == c:
                i += 1
            ans[ord[(u, v)]] = i
            res = max(res, dfs(u, i))
    res = c if res == -1 else res
    res = max(i, res)
    return res

N = int(input())
e = [[] for i in range(N)]
es = defaultdict(int)
ord = defaultdict(int)
ans = [None] * (N-1)
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    e[a].append(b)
    e[b].append(a)
    es[(a, b)] = es[(b, a)] = -1
    ord[(a, b)] = ord[(b, a)] = i
used = [1] * N
print(dfs(0, 0))
print(*ans, sep = '\n')

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
dc={}
g,c=GI(n,n-1)
for a,b in c:
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        


v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col

                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)

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

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

e = [[] for _ in range(n)]

p = [0] * n
c = [0] * n
d = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0

q = [0]
p[0] = -1

while q:
    x = q.pop()
    temp = c[x]
    color = 1
    me = max(me, len(e[x]))
    
    for y in e[x]:
        if color == temp:
            color += 1
        if d[y] == 0:
            q.append(y)
            c[y] = color
            p[y] = x
            color += 1
    d[x] = 1




print(me)

for a, b in ab:
    if p[a] == b:
        print(c[a])
    else:
        print(c[b])

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

N = int(sys.stdin.buffer.readline())

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

K = max(len(l) for l in neighbor)
print(K)
ans = [-1]*(N-1)

def dfs(current_point, parent_point, parent_edge_color):
    color = 1
    for next_point, idx in neighbor[current_point]:
        if next_point != parent_point:
            if parent_edge_color == color:
                color += 1
            ans[idx] = color
            dfs(next_point, current_point, color)
            color += 1

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    b-=1
    bi[i]=b
    children[a-1].append(b)

queue = deque([0])
colors = [0] * N

while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    b-=1
    bi[i]=b
    children[a-1].append(b)

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    bi[i]=b-1
    children[a-1].append(bi[i])

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    bi[i]=b-1
    children[a-1].append(b-1)

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

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

Solution (Python):
n = int(input())
dim = [0 for _ in range(n+1)] 
parent = [0 for _ in range(n+1)] 
col = [ 0 for _ in range(n+1)]  
using = [[] for _ in range(n+1)]
AB = []
for i in range(n-1):
    a, b = map(int, input().split())
    AB.append([a, b, i])
    parent[b] = a
    dim[a] += 1
    dim[b] += 1

AB_sorted = sorted(AB)
prev_a = -1
for j in range(n-1):
    a = AB_sorted[j][0]
    b = AB_sorted[j][1]
    index = AB_sorted[j][2]
    if a != prev_a:
        paint = 1
    
    while paint == col[a] or paint in using[a]:
        paint += 1
    
    col[b] = paint
    using[a].append(paint)
    AB[index].append(paint) 
    prev_a = a

print(max(dim))
for i in range(n-1):
    print(AB[i][3])

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

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

ans = [None]*(N-1)
def dfs(cur, p_color, p=-1):
    color = 1
    for (to, i) in graph[cur]:
        if to == p: continue
        if color == p_color:
            color = color+1
        ans[i] = color
        dfs(to, color, p=cur)
        color = color+1

dfs(0, -1)
print(max(ans))
[print(a) for a in ans]

Solution (Python):
import sys

input = sys.stdin.readline
N=int(input());AB=[tuple(map(int,input().split())) for _ in range(1,N)]

co=[0 for _ in range(N)]
prev=0
color=1
for a,b in sorted(AB):
  if prev!=a:
    color=1
  if co[a-1]==color:
    color+=1
  co[b-1]=color
  prev=a
  color+=1

print(max(co))
for _,b in AB:
  print(co[b-1])

Solution (Python):
def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    keys = [tuple(int(i)-1 for i in input().split()) for _ in range(N-1)]
    for e in keys:
        G[e[0]].append(e[1])
        G[e[1]].append(e[0])
    max_deg = 0
    for g in G:
        max_deg = max(max_deg, len(g))
    edge_color = {k: 0 for k in keys}

    G_color = ['WHITE' for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            c = 0
            if G_parent[u] != "NIL":
                c = ((edge_color[(G_parent[u], u)])+1) % max_deg
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = c
                    c = (c+1) % max_deg
            G_color[u] = 'BLACK'

    bfs(0)
    print(max_deg)
    for k in keys:
        print(edge_color[k] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
ans = [0]*(N-1)

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

print(max([len(x) for x in edge]))

que = [[0,0]]
while(que):
    p_num,p_color = que.pop()
    color = 1
    for c_num,edgenum in edge[p_num]:
        if ans[edgenum] != 0:
            continue
        if color == p_color:
            color += 1
        ans[edgenum] = color
        que.append([c_num,color])
        color += 1
for i in range(N-1):
    print(ans[i])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

stack = deque([0])
parent = [None]*n
colors = [0]*n
while stack:
    node = stack.popleft()
    color = 1
    for child in graph[node]:
        if child == parent[node]:
            continue
        parent[child] = node
        if color == colors[node]:
            color += 1
        colors[child] = color
        color += 1
        stack.append(child)

 
k = max(colors)
print(k)
for a, b in ab:
    if (a-1) == parent[b-1]:
        print(colors[b-1])
    else:
        print(colors[a-1])