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
sys.setrecursionlimit(10 ** 6)

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

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

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

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

from collections import deque

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

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

    q = deque([(0, -1, -1)])
    memo = {}
    max_color = 0
    while len(q) > 0:
        current, v_pre, c_pre = q.popleft()
        color = 1
        for nv in E[current]:
            if nv == v_pre: continue
            if color == c_pre:
                color += 1
            q.append((nv, current, color))
            memo[(min(nv, current), max(nv, current))] = color
            max_color = max(max_color, color)
            color += 1
    

    print(max_color)
    for t in out:
        print(memo[t])

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())
l=[list(nii()) for i in range(n-1)]

tree=[[] for i in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

col=[-1 for i in range(n)]
col[0]=0

que=deque()
que.append(0)

ans_dict={}
while que:
  x=que.popleft()

  t_col=1
  for i in tree[x]:
    if col[i]!=-1:
      continue
    if t_col==col[x]:
      t_col+=1
    que.append(i)
    col[i]=t_col
    ans_dict[(x+1,i+1)]=t_col
    ans_dict[(i+1,x+1)]=t_col
    t_col+=1

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a1,list1 in l:
    color=1
    for b1 in list1:
        if a1>b1:
            a,b=b1,a1
        else:
            a,b=a1,b1

        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1

print(m)
for line in ab:
    print(d2[line])

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a1,list1 in l:
    color=1
    for b1 in list1:
        if a1>b1:
            a,b=b1,a1
        else:
            a,b=a1,b1

        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1

print(m)
ans=[]
for line in ab:
    ans.append(d2[line])
print(*ans,sep="\n")

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for node,list1 in l:
    a=node
    color=1

    for b1 in list1:
        if node>b1:
            a,b=b1,node
        else:
            a,b=node,b1

        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1

print(m)
for line in ab:
    print(d2[line])

Solution (Python):
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
lis = []
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
    lis.append([a,b,i])
mx = 0
for i in range(n):
    ki[i].sort()
    mx = max(mx,len(ki[i]))
lis = sorted(lis, key=lambda x:x[0])
lis = sorted(lis, key=lambda x:x[1])
lis2 = [[] for i in range(n)]
cnt = 0
for i in range(n-1):
    lis2[lis[i][0]].append(lis[i])



def bfs(ki,lis2):
    d = [True] * n
    que = deque([(0,-1)])
    d[0] = False
    while len(que) != 0:
        val = que.popleft()
        cnt = 1
        cnt2 = 0
        for i in range(len(ki[val[0]])):
            if d[ki[val[0]][i]] == True:
                d[ki[val[0]][i]] = False

                
                if val[1] == cnt:
                    cnt += 1
                lis2[val[0]][cnt2].append(cnt)
                que.append([ki[val[0]][i],cnt])
                cnt += 1
                cnt2 += 1

    return lis2
lis2 = bfs(ki,lis2)

val = 0
for i in range(n):
    val = max(len(ki[i]),val)
print(val)
lis = []
for i in range(n):
    for j in range(len(lis2[i])):
        lis.append(lis2[i][j])
lis = sorted(lis,key=lambda x:x[2])
for i in range(n-1):
    print(lis[i][3])

Solution (Python):
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
lis = []
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
    lis.append([a,b,i])
mx = 0
for i in range(n):
    ki[i].sort()
    mx = max(mx,len(ki[i]))
lis = sorted(lis, key=lambda x:x[0])
lis = sorted(lis, key=lambda x:x[1])
lis2 = [[] for i in range(n)]
cnt = 0
for i in range(n-1):
    lis2[lis[i][0]].append(lis[i])



def bfs(ki,lis2):
    d = [True] * n
    que = deque([(0,-1)])
    d[0] = False
    while len(que) != 0:
        val = que.popleft()
        cnt = 1
        cnt2 = 0
        for i in range(len(ki[val[0]])):
            if d[ki[val[0]][i]] == True:
                d[ki[val[0]][i]] = False

                
                if val[1] == cnt:
                    cnt += 1
                lis2[val[0]][cnt2].append(cnt)
                que.append([ki[val[0]][i],cnt])
                cnt += 1
                cnt2 += 1

    return lis2
lis2 = bfs(ki,lis2)

val = 0
for i in range(n):
    val = max(len(ki[i]),val)
print(val)
lis = []
for i in range(n):
    for j in range(len(lis2[i])):
        lis.append(lis2[i][j])
lis = sorted(lis,key=lambda x:x[2])
for i in range(n-1):
    print(lis[i][3])

Solution (Python):
import sys
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
def f(i,r):
    c=1
    for (x,y) in T[i]:
        c+=(c==r)
        C[y]=c
        f(x,c)
        c+=1
f(0,0)
print(max(C))
for c in C:
    print(c)

Solution (Python):
def f(u, i, d, t, vis):
    if vis[u]:
        return
    vis[u] = True
    z = t[u]

    c = 1
    for v in z:
        if vis[v]:
            continue
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t, vis)
        c += 1


def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        t[j].append(i)
        m.append([i, j])
    d = defaultdict(dict)
    vis = [False for _ in range(n + 1)]
    f(1, len(t[1]) + 1, d, t, vis)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t)) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
N = int(input())
ab = {}
abl = []
path = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
    abl.append((a-1,b-1))
    ab[(a-1,b-1)] = 0
color = [0]*N
color[0] = -1
q = deque([])
q.append(0)
max = 0

while len(q)>0:
    cn = q.popleft()
    ccolor = color[cn]
    ncolor = 1
    for i in path[cn]:
        if color[i] == 0:
            if ccolor != ncolor:
                color[i] = ncolor
                ab[(cn,i)] = ncolor
                ncolor += 1
            else:
                color[i] = ncolor+1
                ab[(cn,i)] = ncolor+1
                ncolor += 2
            if color[i] > max:
                max = color[i]
            q.append(i)
print(max)
for i in abl:
    print(ab[i])

Solution (Python):
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())
l=[list(nii()) for i in range(n-1)]

tree=[[]for _ in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(b)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

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

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.pop()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Solution (Python):
from collections import deque

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

tree=[[]for _ in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(b)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

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

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.popleft()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Solution (Python):
from collections import deque

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

tree=[[]for _ in range(n)]
for a,b in l:
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(b)

ans_num=0
for i in tree:
  ans_num=max(ans_num,len(i))

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

seen=set()
seen.add(0)

ans_dict={}
while dq:
  x,color=dq.pop()

  i=0
  for nx in tree[x]:
    if nx in seen:
      continue

    i+=1
    if i==color:
      i+=1

    seen.add(nx)
    dq.append((nx,i)),
    ans_dict[x+1,nx+1]=i
    ans_dict[nx+1,x+1]=i

print(ans_num)
for i in l:
  print(ans_dict[tuple(i)])

Solution (Python):
from collections import deque
n = int(input())

d = deque()
dic = {}
dic_l = {}

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

    if(a in dic):
        dic[a].append(b)
    else:
        dic[a] = [b]
    
    if(b in dic):
        dic[b].append(a)
    else:
        dic[b] = [a]
    
    l = max(a,b)
    s = min(a,b)
    dic_l[s,l] = i



mx = 0
for k in dic:
    mx = max(mx,len(dic[k]))


col = [i+1 for i in range(mx)]
ans = [0 for _ in range(n-1)]
seen = {1}

cnt = 0
tmp = deque()
for i in dic[1]:
    if not(i in seen):
        d.append(i)
        seen.add(i)
        tmp.append(1)
        tmp.append(i)

    load_key = (1,i)
    l_num = dic_l[load_key]
    ans[l_num] = col[cnt]
    cnt += 1


while d:
    nxt = d.popleft()
    tmp_1 = tmp.popleft()
    tmp_2 = tmp.popleft()
    ng = (tmp_1,tmp_2)
    
    ng_col = ans[dic_l[ng]]
    cnt = 0
    for i in dic[nxt]:
        if not(i in seen):
            d.append(i)
            seen.add(i)
            tmp.append(nxt)
            tmp.append(i)
            l = max(nxt,i)
            s = min(nxt,i)
            load_key = (s,l)
            l_num = dic_l[load_key]
            while cnt+1 == ng_col:
                cnt += 1
            ans[l_num] = col[cnt]
            cnt += 1

print(mx)
for s in ans:
    print(s)

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

import sys
sys.setrecursionlimit(10 ** 7)

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


max_color=0
for graph_i in graph:
    max_color=max(max_color, len(graph_i))
print(max_color)

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

def dfs(v, color, pre):
    if color!=0:
        nc=0
    else:
        nc=1
    for e in graph[v]:
        
        if e[0]==pre:
            continue
        colors[e[1]]=nc
        dfs(e[0],nc,v)
        nc+=1
        if nc==color:
            nc+=1

dfs(0,-1,-1)

for c in colors:
    print(c+1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

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

    seen = [False]*N
    res = [0]*M

    def dfs(G, v):
        col = 1
        parent_col = -1
        if col == parent_col:
            col += 1
        seen[v] = True
        stack = deque([(v, -1)])
        while stack:
            v, parent_col = stack.pop()
            col = 1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if col == parent_col:
                    col += 1
                res[edge_ind] = col
                seen[next_v] = True
                stack.append((next_v, col))
                col += 1

    
    dfs(G, 0)
    print(max(res))
    for i in res:
        print(i)


resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

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

    seen = [False]*N
    res = [0]*M

    def dfs(G, v, parent_col):
        col = 1
        if col == parent_col:
            col += 1
        seen[v] = True
        stack = deque([(v, -1)])
        while stack:
            v, parent_col = stack.pop()
            col = 1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if col == parent_col:
                    col += 1
                res[edge_ind] = col
                seen[next_v] = True
                stack.append((next_v, col))
                col += 1

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


resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    from collections import deque

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

    seen = [False]*N
    res = [0]*M


    def dfs(G, v, pc):
        color = 1
        if color == pc:
            color += 1
        seen[v] = True
        stack = deque([(v,-1)])
        while stack:
            v,pc = stack.pop()
            color=1
            for next_v, edge_ind in G[v]:
                if seen[next_v]:
                    continue
                if color == pc:
                    color += 1
                res[edge_ind] = color
                seen[next_v] = True
                stack.append((next_v,color))
                color+=1

            

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



resolve()

Solution (Python):
import sys
from collections import deque
from operator import itemgetter

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    al = [[] for _ in range(n)]
    e = dict()
    for i in range(n - 1):
        a, b = [int(j) - 1 for j in read().split()]
        al[a].append(b)
        al[b].append(a)
        e[(a, b)] = i
    v, k = 0, 0
    for i in range(n):
        if len(al[i]) > k:
            v = i
            k = len(al[i])
    print(k)
    sn = deque([(v, 0)])
    sd = set()
    ce = dict()
    while sn:
        v, cv = sn.popleft()
        sd.add(v)
        ci = 1
        for vn in al[v]:
            if vn in sd:
                continue
            if ci == cv:
                ci += 1
            if (v, vn) in e:
                ce[(v, vn)] = ci
            else:
                ce[(vn, v)] = ci
            sn.append((vn, ci))
            ci += 1
    for k, _ in sorted(e.items(), key=itemgetter(1)):
        print(ce[k])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def bfs(idx,k,colored):
  q = deque()
  visited[idx] = True
  q.append(idx)
  while q:
    r = q.pop()
    color = 0
    for n in graph[r].keys():
      if not visited[n]:
        if color == colored[r]: color+=1
        colored[n] = color
        graph[r][n] = color
        graph[n][r] = color
        color += 1

        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
colored = [-1]*(N+1)
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k,colored)
print(k)
for a,b in ab:
  print(graph[a][b]+1)

Solution (Python):
from collections import deque
n = int(input())

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

que = deque([0])
ans = [0] * (n - 1)
visited = [-1] * n
visited[0] = 0
while que:
    a = que.popleft()
    c = 1
    for b in graph[a]:
        if visited[b] < 0:
            if visited[a] == c:
                c += 1
            visited[b] = c
            ans[edges[(a, b)]] = c
            c += 1
            que.append(b)

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

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


color_max =0
connection ={i:deque() for i in range(1,N+1)}
edge_color={}
A =[(-1,-1)]*N
for i in range(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)
    edge_color[(a,b)] =-1
    A[i] =(a,b)
    color_max =max(color_max, len(connection[a]) , len(connection[b]))


passed =set()

parent ={i:-1 for i in range(1,N+1)}
parent[1] =0
dq =deque()
dq.append(1)
color =0

edge_color[(0,1)] =0

while dq:
    now =dq.popleft()
    passed.add(now)
    na_max =max(parent[now],now)
    na_min =min(parent[now],now)
    i_color =edge_color[(na_min,na_max)]
    for next in connection[now]:
        if next in passed:
            continue
        else:
            i_color +=1
            n_max =max(now,next)
            n_min =min(now,next)
            edge_color[(n_min,n_max)] =(i_color)% color_max 
            dq.append(next)
            parent[next] =now
print(color_max)
del edge_color[(0,1)]
for i in range(1,N):
    print(edge_color[A[i]] +1 )

Solution (Python):

from collections import deque
d=deque()
e=deque()

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

K=0
d.append(1)
visited=[False for i in range(N+1)]
color=[-1 for i in range(N+1)]
visited[1]=True
color[1]=-1
dic={}
while d:
    while d:
        x=d.popleft()
        par_color=color[x]
        c=1
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                e.append(node)                
                if c!=par_color:
                    color[node]=c
                    dic[(x,node)]=c
                elif c==par_color:
                    c+=1
                    color[node]=c
                    dic[(x,node)]=c
                c+=1
    if e:
        d=e
        e=deque()

A=max(color)
print(A)
for que in D:
    a,b=que
    if (a,b) in dic.keys():
        print(dic[que])
    else:
        print(dic[(b,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())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])

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

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

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

Solution (Python):
from collections import deque
import sys

input = sys.stdin.buffer.readline
n = int(input())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append((b, i + 1))
    graph[b].append((a, i + 1))
par = [-1] * (n + 1)
que = deque([(1, -1, -1, -1)])  
color = [-1] * (n)
num = 0  
while que:
    v, c, p, hen = que.popleft()
    par[v] = p
    color[hen] = c
    cnt = 0
    for i in range(len(graph[v])):
        u, hen_num = graph[v][i]
        if u == par[v]:
            continue
        cnt += 1
        if cnt == c:
            cnt += 1
        color[hen_num] = cnt
        num = max(num, cnt)
        que.append((u, cnt, v, hen_num))
print(num)
print(*color[1:], sep="\n")

Solution (Python):
import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
start = 0
color = [[] for _ in range(N+1)]
node[1] = 0
while(True):
    if que.empty():
        break
    before = start
    start = que.get()
    col =1
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
        if edge[i[1]] == -1:
            if col == node[start]:
                col += 1
            edge[i[1]] = col
            node[i[0]] = col
            if col > maxi:
                maxi = col
            col +=1
            
print(maxi)
for i in edge[1:]:
    print(i)

Solution (Python):
from collections import deque

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

q = deque([0])

chk = [False] * n
chk[0] = True

res = [0] * n
par = [0] * n
while q:
    x = q.popleft()
    cnt = 1
    for y in g[x]:
        if chk[y]:
            continue
        if res[x] == cnt:
            cnt += 1
        res[y], par[y], chk[y] = cnt, x, True
        cnt += 1
        q.append(y)

ans = []
for a, b in ab:
    if par[a] == b:
        ans.append(res[a])
    else:
        ans.append(res[b])

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

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

color = [0]*N
visited = [False]*N
visited[0] = True
queue = deque([1])
ans = [0]*(N-1)
while queue:
    now = queue.popleft()
    cnt = 1
    for n, e in adj[now-1]:
        if visited[n-1]:
            continue
        if color[now-1] == cnt:
            cnt += 1
        color[n-1] = cnt
        visited[n-1] = True
        ans[e] = cnt
        cnt += 1
        queue.append(n)
print(max(color))
print(*ans, sep='\n')

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

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

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

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

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

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

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)

col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k 

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

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

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0]*n
    dq.append(0)
    done[0] = 1
    edgecolor = [0]*(n-1)

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

if __name__ == '__main__':
    main()

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

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0 for _ in range(n)]
    dq.append(0)
    done[0] = 1
    edgecolor = [0 for _ in range(n-1)]

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

if __name__ == '__main__':
    main()

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

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

    dq = deque()    
    done = [0 for _ in range(n)]
    dq.append(0)
    done[0] = 1
    edgecolor = [0 for _ in range(n-1)]

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for e in g[v]:
            nx = e.to
            edge_id = e.id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

if __name__ == '__main__':
    main()