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 random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

if __name__ == "__main__":
    main()

Solution (Python):


import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
z = []
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    g[a].append(b)
    g[b].append(a)
    if a<b:
        z.append((a,b))
    else:
        z.append((b,a))

from collections import deque

parent = [0]*n
mc = 0
en = dict()

q = deque()
used = [0]*n
q.append(0)
used[0] = 1
while q:
    p = q.popleft()
    color = 0
    for i in g[p]:
        if used[i] != 1:
            color += 1
            used[i] = 1
            if color==parent[p]:
                color += 1
            if p<i:
                en[(p,i)]=color
            else:
                en[(i,p)]=color
            parent[i] = color
            q.append(i)
    mc = max(mc,color)

print(mc)
for i in z:
    print(en[i])

Solution (Python):
from collections import deque
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
lines=[[] for i in range(n)]
for a,b in ab:
  lines[a-1].append(b-1)
q=deque([0])
color=[0]*n
while q:
  x=q.popleft()
  c=1
  for y in lines[x]:
    if c==color[x]:
      c+=1
    color[y]=c
    c+=1
    q.append(y)
print(max(color))
for i in range(n-1):
  print(color[ab[i][1]-1])

Solution (Python):

n=int(raw_input())
e={}
t=[[] for i in range(n)]
c=[1]*(n-1)
for i in range(n-1):
 a,b=map(int,raw_input().split())
 a,b=a-1,b-1
 t[a].append(b)
 e[(a,b)]=i
cp=[[] for i in range(n)]
for i in range(n):
 x=1
 for vc in t[i]:
  while x in cp[i]:
   x+=1
  c[e[(i,vc)]]=x
  cp[vc].append(x)
  x+=1
print max(c)
for i in range(len(c)):
 print c[i]

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

n=int(input())
L=[[] for i in range(n)]
V=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
    V.append([a,b])
k=max(len(l) for l in L)

C=[-1]*n
D=[-1]*n
C[0]=0
D[0]=0
q=queue.Queue()
q.put(0)
while not q.empty():
    now=q.get()
    c=C[now]
    for i in L[now]: 
        if D[i]==-1:
            c=(c+1)%k
            C[i]=c
            D[i]=D[now]+1
            q.put(i)

print(k)
for v in V:
    if D[v[0]]>D[v[1]]:
        print(C[v[0]]+1)
    else:
        print(C[v[1]]+1)

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

n=int(input())
L=[[] for i in range(n)]
V=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
    V.append([a,b])
k=max(len(l) for l in L)
C=[-1]*n
D=[-1]*n
def dfs(s,p=-1,d=0): 
    c=C[s]
    for i in L[s]: 
        if i!=p: 
            c=(c+1)%k
            C[i]=c
            D[i]=d
            dfs(i,s,d+1) 

dfs(0)
print(k)
for v in V:
    if D[v[0]]>D[v[1]]:
        print(C[v[0]]+1)
    else:
        print(C[v[1]]+1)

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

import sys
sys.setrecursionlimit(10**6)

def dfs(v, c, p):
    k = 1
    for _v, _id in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())

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



def dfs(v, c, p):
    k = 1
    for _v, _id  in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

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

dfs(0, -1, -1)
print(max(C))
for i in C:
    print(i)

Solution (Python):


from collections import deque


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

    return n, edges, edge_list


def submit():
    n, edges, edge_list = read_input()

    
    
    
    curr_color_max = -1
    color = {}
    q = deque()
    q.appendleft((0, 0))

    while len(q):
        curr, from_color = q.pop()
        color_count = 1
        for e in edges[curr]:
            key = (min(curr, e), max(curr, e))
            if key in color.keys():
                continue
            else:
                if color_count == from_color:
                    color_count += 1
                if color_count > curr_color_max:
                    curr_color_max = color_count     
                color[key] = color_count
                q.appendleft((e, color_count))
                color_count += 1

    print(curr_color_max)
    for e in edge_list:
        print(color[e])


if __name__ == "__main__":
    submit()

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


def dfs(v, p, p_col, tree, res):
    col = 1
    for u, id in tree[v - 1]:
        if u == p:
            continue
        if col == p_col:
            col += 1
        res[id] = col
        dfs(u, v, col, tree, res)
        col += 1


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

    ans = [0 for _ in range(n-1)]
    dfs(1, -1, -1, tree, ans)
    print(max(ans))
    print("\n".join(map(str, ans)))


if __name__ == '__main__':
    main()

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

A=[[] for _ in range(N-1)]
B=[0]*N
C=[0]*N
D=[0]*N

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

for i in range(N-1): 
    c=0
    for j in A[i]:
        while True:
            c+=1
            if c!=B[i]:
                B[j-1]=c
                break

print(max(B))            

for i in range(1,N):
    D[C[i]]=B[i]

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

Solution (Python):
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
el = defaultdict(lambda :[])
for i in range(n-1):
    a, b = iip()
    el[a-1].append((b-1, i))
    el[b-1].append((a-1, i))



def main():
    color = [None for i in range(n-1)]
    cmax = 0
    que = deque()
    que.append((0, 0))

    while que:
        parent, used_color =que.popleft()
        children = el[parent]
        cn = 1

        for child, edge_num in children:
            el[child].remove((parent, edge_num))

            if cn == used_color:
                cn += 1
            color[edge_num] = cn
            cmax = max(cn, cmax)
            que.append((child, cn))
            
            cn += 1



    print(cmax)
    for i in color:
        print(i)



main()

Solution (Python):

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

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

    d = deque()
    d.append(1)

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

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    print(max(ans))
    print('\n'.join([str(ans[b]) for _, b in ab]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

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

    d = deque()
    d.append(1)

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

    parent = [-1] * (N+1)
    parent[1] = 1

    while d:
        p = d.popleft()
        c = 0
        for g in graph[p]:
            if parent[g] > 0 or g == parent[g]:
                continue
            c += 1
            if c == ans[p]:
                c += 1
            ans[g] = c

            parent[g] = p
            d.append(g)

    print(max(ans))
    for _, b in ab:
        print(ans[b])

if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
ans = [0] * (n-1)
abi = [[] for _ in range(n+1)]

import sys
sys.setrecursionlimit(4100000)
for i,(a,b) in enumerate(ab):
    abi[a].append((i,b))
    abi[b].append((i,a))

def dfs(v,parent=-1,color=-1):
    k=1
    for i in abi[v]:
        if parent==i[1]:continue
        if(k==color):k+=1
        ans[i[0]]=k
        k+=1
        dfs(i[1],v,ans[i[0]])

dfs(1)

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

Solution (Python):

import queue

def swap(x, y):
    if x > y:
        x, y = y, x
    return (x, y)

n = int(input())

edges = [[] for _ in range(n)]
edges_dict = {}
ans = [0 for _ in range(n-1)]
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    edges_dict[(a-1, b-1)] = i
    
k, k_idx = 0, 0
for i in range(n):
    if len(edges[i]) > k:
        k = len(edges[i])
        k_idx = i

que = queue.Queue()
que.put((k_idx, 0))
while not que.empty():
    q, x = que.get()
    tmp = 1
    for to in edges[q]:
        if ans[edges_dict[swap(q, to)]] != 0:
            continue
        if tmp == x:
            tmp += 1
        ans[edges_dict[swap(q, to)]] = tmp
        que.put((to, tmp))
        tmp += 1
            
print(k)
print(*ans, sep= '\n')

Solution (Python):
n=int(input())
X=[[] for _ in range(n)]

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

ANS=[0]*(n-1)
VC=[0]*n
k=1
for v,c in enumerate(X):
    t=1
    for b, i in c:
        if VC[v]==t:
            t+=1
        VC[b]=t
        ANS[i]=t
        k=max(k,t)
        t+=1
print(k)
for i in range(n-1):
    print(ANS[i])

Solution (Python):
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
lines = [[] for _ in range(N+1)]
for a, b in ab:
    lines[a].append(b)
    
q = deque([1])
color = [0]*(N+1)
while q:
    x = q.popleft()
    c = 1
    for y in lines[x]:
        if c == color[x]:
            c += 1
        color[y] = c
        c += 1
        q.append(y)
print (max(color))
for i in range(N-1):
    print (color[ab[i][1]])

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
G = None
ans = None

def dfs(v, parent_c=-1, parent_id=-1):
    global G, ans
    k = 1
    for i in range(len(G[v])):
        edge_id, to = G[v][i]['edge_id'], G[v][i]['to']
        if to == parent_id: continue
        if k == parent_c: k+=1
        ans[edge_id] = k
        k += 1
        dfs(to, parent_c=ans[edge_id], parent_id=v)

def main():
    global G, ans
    N = int(input())
    G = [[] for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    for edge_id in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append({'to': b, 'edge_id': edge_id})
        G[b].append({'to': a, 'edge_id': edge_id})
    
    dfs(0)
    print(max(ans))
    for a in ans:
        print(a)

main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
G = None
ans = None

def dfs(v, parent_c=-1, parent_id=-1):
    global G, ans
    k = 1
    for i in range(len(G[v])):
        edge_id, to = G[v][i]['edge_id'], G[v][i]['to']
        if to == parent_id: continue
        if k == parent_c: k+=1
        ans[edge_id] = k
        k += 1
        dfs(to, parent_c=ans[edge_id], parent_id=v)

def main():
    global G, ans
    N = int(input())
    G = [[] for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    for edge_id in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append({'to': b, 'edge_id': edge_id})
        G[b].append({'to': a, 'edge_id': edge_id})
    
    dfs(0)
    print(max(ans))
    for a in ans:
        print(a)

main()

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

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





def d(index, color):
    cnt = 1
    for (t, jid) in ki[index]:
        if cnt == color:
            cnt += 1
        ans[jid] = cnt
        d(t, cnt)
        cnt += 1


d(0, 0)
print(max(ans))
for i in ans:
    print(i)

Solution (Python):
from collections import deque
n = int(input())
e = [[] for i in range(n)]
num = 0

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

    e[a-1].append([b-1,i])
    e[b-1].append([a-1,i])
    num = max(num,len(e[a-1]),len(e[b-1]))

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

q = deque([])
q.append((0,-1))

while q:
    bef,pn = q.popleft()
    c = 0
    for nex in e[bef]:
        if ans[nex[1]] == -1:
            c += 1
            if c == pn:
                c += 1
            ans[nex[1]] = c
            q.append((nex[0],c))

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

Solution (Python):
from collections import deque
n = int(input())
e = [[] for i in range(n)]
num = 0

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

    e[a-1].append([b-1,i])
    e[b-1].append([a-1,i])
    num = max(num,len(e[a-1]),len(e[b-1]))

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

q = deque([])
q.append((0,-1))

while q:
    bef,pn = q.popleft()
    c = 0
    for cn,nex in enumerate(e[bef]):
        if ans[nex[1]] == -1:
            c += 1
            if c == pn:
                c += 1
            ans[nex[1]] = c
            q.append((nex[0],c))

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

Solution (Python):
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = int(input())

edge = [tuple(map(int, input().split())) for _ in range(n-1)]
adj = [set() for _ in range(n)]
ans_dict = {}
c_max = 1
for a, b in edge:
    adj[a-1].add(b-1)

que = deque()
c = 1
for l in adj[0]:
    
    que.append([l,c])
    ans_dict[(1,l+1)] = c
    c += 1
c_max = max(c-1, c_max)
while que:
    c = 1
    
    new_v = que.popleft()
    for l in adj[new_v[0]]:
        if c == new_v[1]:
            c += 1
        
        que.append([l,c])
        ans_dict[(new_v[0]+1, l+1)] = c
        c += 1
    c_max = max(c-1, c_max)

print(c_max)
for l in edge:
    print(ans_dict[l])

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

ans = {(-1, 0): -1}
que = {(-1, 0)}
while que:
    queque = set()
    for p, v in que:
        c = 1
        for w in connect[v]:
            if w != p:
                if c == ans[(p, v)]:
                    c += 1
                ans[(v, w)] = c
                queque.add((v, w))
                c += 1
    que = queque
pri = [0] * (n-1)
for i, (a, b) in enumerate(edge):
    a -= 1
    b -= 1
    if (a, b) in ans:
        pri[i] = ans[(a, b)]
    else:
        pri[i] = ans[(b, a)]
print(max(pri))
for x in pri:
    print(x)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for j in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append((b, j))
    e[b].append((a, j))

co = [0]*(n-1)


def dfs(i=0, r=-1, dis=-1):
    global co
    c = 1
    for j in e[i]:
        if j[0] == r:
            continue
        if c == dis:
            c += 1
        co[j[1]] = c
        dfs(j[0], i, c)
        c += 1


dfs()

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

Solution (Python):
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)

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

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

print(max(MA))
for i in range(N-1):
    print(edge[ans[i]])

Solution (Python):
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)
M = 0

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

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                M = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    M = max(M,MA[now])
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

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

Solution (Python):
import sys
import resource
sys.setrecursionlimit(10**5)
n = int(input())
l = [[] for _ in range(n+1)]
s = [0 for _ in range(n+1)]
ll = []
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append([bi,i])
  l[bi].append([ai,i])
  s[ai] += 1
  s[bi] += 1
mx = 0
for i in range(1,n+1):
  if s[i] > mx:
    mx = s[i]
    mxi = i
print(mx)
ans = [0 for _ in range(n-1)]
def dfs(a,b,c):
  i = 1
  for h,j in l[a]:
    if h != b:
      if i == c:
        i += 1
      ans[j] = i
      dfs(h,a,i)
      i += 1
  return
dfs(mxi,0,0)
for x in ans:
  print(x)

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    AB=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        AB.append(str(a)+" "+str(b))

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    ans=dict()
    
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                ans[str(min(now,x))+" "+str(max(now,x))]=color
                color+=1
        color-=1
        K=max(K,color)

    
    print(K)
    for key in AB:
        print(ans[key])
        
if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    B=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        B.append(b)

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                color+=1
        color-=1
        K=max(K,color)

    print(K)
    for x in B:
        print(link[x])
if __name__=="__main__":
    main()

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

def dfs(x, c=-1, p=-1):
    k = 1
    for y, ei in G[x]:
        if y == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k; k+=1
        dfs(y, ans[ei], x)

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

dfs(0)
mx = 0
for g in G:
    mx = max(mx, len(g))
print(mx)
for a in ans:
    print(a)

Solution (Python):


import queue

N = int(input())

e = []
v2e = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    v2e[a].append((b, i))
    v2e[b].append((a, i))
    
count = 0
f = [False] * N
f[0] = True
c = [-1] * (N - 1)
q = queue.Queue()
q.put((-1, 0))
while q.qsize() > 0:
    ie, v = q.get()
    t = 0
    for i, j in v2e[v]:
        if f[i] == False:
            if t == ie:
                t += 1
            q.put((t, i))
            c[j] = t
            f[i] = True
            t += 1
                
print(max(c) + 1)
for i in range(len(c)):
    print(c[i] + 1)

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

N = int(input())

edges = [[] for i in range(N+1)]
color = [0 for i in range(N-1)]

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

root = -1
MAX = 0

for i in range(N+1):
    if MAX < len(edges[i]):
        root = i
        MAX = len(edges[i])

K = MAX

def dfs(parent,v,c):
    flag = 0
    for i in range(len(edges[v])):
        if edges[v][i][0] == parent:
            flag = 1
        else:
            color[edges[v][i][1]] = (c+i+1-flag)%K
            dfs(v,edges[v][i][0],(c+i+1-flag)%K)

dfs(-1,root,0)

print(K)

for i in color:
    if i == 0:
        print(K)
    else:
        print(i)

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

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



col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  visited[v] = True
  
  
  
    
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

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

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



col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  
  
  
    
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

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

def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    l=[[] for _ in range(n+1)]
    for i in range(n-1):
        l[ab[i][0]].append(ab[i][1])
    col=[0]*(n+1)
    chk=deque([1])
    while chk:
        x=chk.popleft()
        c=0
        for y in l[x]:
            c+=1
            if col[x]==c:
                c+=1
            col[y]=c
            chk.append(y)
    print(max(col))
    for i in range(n-1):
        print(col[ab[i][1]])
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
E = [[] for _ in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
color = [0]*(N+1)

start = 1
q = deque([start])
while(q):
    v = q.pop()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == color[v])
        color[u] = c
        q.append(u)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])

Solution (Python):
from collections import deque
n=int(input())
A=[]
B=[0]*(n-1)
G=[[] for i in range(n)]
GG=[[0]*2 for i in range(n-1)]
for i in range(n-1):
  a,b=map(int,input().split())
  GG[i]=[a,b]
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  A.append(a*10**6+b)
D=dict(zip(A,B))
ans=0
for i in range(n):
  if len(G[i])>ans:
    ans=len(G[i])
    a=i
print(ans)
VC=[10**6]*n 

E=[0]*n
E[a]=1
F=deque([a])
while len(F)>0:
  s=F[0]
  F.popleft()
  c=1
  for i in range(len(G[s])):
    if E[G[s][i]]==0:
      F.append(G[s][i])
      E[G[s][i]]=1
      if c==VC[s]:
        c=c+1
      VC[G[s][i]]=c
      t=s
      D[min(s+1,G[s][i]+1)*10**6+max(s+1,G[s][i]+1)]=VC[G[s][i]]
      c=c+1
for i in range(n-1):
  print(D[GG[i][0]*10**6+GG[i][1]])

Solution (Python):
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    ab = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
        ab.append([a, b])
    queue = deque([1])

    
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

    print(max(color))
    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])


if __name__ == '__main__':
    main()