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):
n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

for i in range(n-1):
    for j in range(2):
        A[i][j] -= 1

M = [[] for i in range(n)]
for i in range(n-1):
    M[A[i][0]].append([A[i][1], i])
    M[A[i][1]].append([A[i][0], i])
    
C = [-1] * n
s = 0
Q = [[0, 0]]
C[0] = 0
while len(Q) > s:
    i = Q[s][0]
    ic = Q[s][1]
    for j in range(len(M[i])):
        if C[M[i][j][0]] == -1:
            C[M[i][j][0]] = ic+1
            Q.append([M[i][j][0], ic+1])

    s += 1

D = []
for i in range(n):
    D.append([C[i], i])
D.sort()
ANS = [0] * (n-1)
NG = [0] * n

for i in range(n):
    c = 1
    v = D[i][1]
    for j in range(len(M[v])):
        if ANS[M[v][j][1]] == 0:
            if NG[v] == c:
                c += 1
            ANS[M[v][j][1]] = c
            NG[M[v][j][0]] = c
            c += 1


print(max(ANS))
for i in range(len(ANS)):
    print(ANS[i])

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    ans = {}
    queue = deque([])
    e = []
    for l in range(N-1):
        temp = list(map(int,input().split()))
        temp[0] -= 1
        temp[1] -= 1
        e.append(tuple(temp))
        ans[(temp[0],temp[1])] = 0
        ans[(temp[1],temp[0])] = 0
        G[temp[0]].append(temp[1])
        G[temp[1]].append(temp[0])
        if l == 0:
            queue.append(temp[0])
    
    nuc = [[0] for _ in range(N)]
    
    auc = []
    
    def bfs(x):
        k = 1
        for i in G[x]:
            if ans[(x,i)] ==0:
                queue.append(i)
                flag = 1
                while flag:
                    if k not in nuc[x]:         
                        ans[(x,i)] = k
                        ans[(i,x)] = k
                        nuc[x].append(k)
                        nuc[i].append(k)
                        if k not in auc:
                            auc.append(k)
                        flag = 0
                    else:
                        k += 1
                    
    while len(queue) > 0:
        next_ = queue.popleft()
        bfs(next_)
    print(len(auc))
    for m in e:
        print(ans[m])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
G = [list() for _ in range(N)]

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

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)

dfs(0)
mx = 0

for i in range(N):
    mx = max(mx,len(G[i]))
print(mx)

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)
N = int(input())
ans = [0] * (N - 1)
AB = []
for i in range(N-1):
    a,b = map(int,input().split())
    AB.append([a-1,b-1])
G = [list() for _ in range(N)]
for i in range(N-1):
    G[AB[i][1]].append([AB[i][0],i])
    G[AB[i][0]].append([AB[i][1],i])

def dfs(v,c = -1,p = -1):
    k = 1
    for i in range(len(G[v])):
        u = G[v][i][0];ei = G[v][i][1]
        if u == p:continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx,len(G[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Solution (Python):

n = int(input())
Ad = [[] for _ in range(n)]
Deg = [0]*n
E = {}
E2 =[]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1
    E[(ai,bi)]=-1
    E[(bi,ai)]=-1
    E2.append((ai,bi))
mx = max(Deg)
print(mx)
E[(0,0)] = -1
P =[-1]*n
from collections import deque
Q = deque()
Q.append(0)
P[0] = 0

while Q:
    v = Q.popleft()
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)

Q = deque()
cnt = 1
for v in Ad[0]:
    E[(0,v)]=cnt
    E[(v,0)]=cnt
    cnt+=1
    Q.append(v)

while Q:
    v = Q.popleft()
    cnt = 1
    for u in Ad[v]:
        if E[(u,v)]<0:
            if cnt==E[(v,P[v])]:
                cnt +=1
            E[(u,v)] = cnt
            E[(v,u)] = cnt
            cnt+=1
            Q.append(u)
for i in range(n-1):
    print(E[E2[i]])

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


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
            rootedTree(root_num,node,tree[root_num],num)


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

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


def rootedTree(node,parent,root,add):
    A.append([node,parent,root,add])
    for root_num,num in root:
        if len(tree[root_num])!=0:
            rootedTree(root_num,node,tree[root_num],num)
        else:
            A.append([root_num,node,tree[root_num],num])


n=int(input())
AB=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
A=[]
tree=[[] for i in range(n+1)]
for a,b,c in AB:
    tree[a] +=[[b,c]]

rootedTree(1,0,tree[1],0)
ans=[0]*n
for node,parent,root,num in A:
    flag=0
    for i,j in enumerate(root):
        if ans[num]==i+1:flag=1
        if flag:
            ans[j[1]]=i+2
            continue
        ans[j[1]]=i+1

print(max(ans))
for i in range(1,n):print(ans[i])

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

data = {}
inputData = []
edges = {}
maxColor = 0
for i in range(N-1):
    a, b = map(int, input().split())
    data[(a, b)] = 0
    inputData.append((a, b))
    if a not in edges:
        edges[a] = []
    if b not in edges:
        edges[b] = []
    edges[a].append(b)
    edges[b].append(a)
    maxColor = max(maxColor, len(edges[a]))

queue = deque([(1, 0)])

while(len(queue)):
    q, c = queue.popleft()
    k = 0
    for v in edges[q]:
        a = min(q,v)
        b = max(q,v)
        if(data[(a, b)]) != 0:
            continue
        k += 1
        data[(a, b)] = c+k
        queue.append((v, c+k))
print(maxColor)
for i in range(N-1):
    print((data[inputData[i]]-1)%maxColor+1)

Solution (Python):
N = int(input())
AB =[]
V = [[] for _ in range(N)]
Edict = dict()
for _ in range(N-1):
    a,b = map(int,input().split())
    AB.append((a-1,b-1))
    V[a-1].append(b-1)
    V[b-1].append(a-1)
K = max(len(V[i]) for i in range(N))
for i in V:
    i.sort()
for i,v in enumerate(V[0]):
    Edict[(0,v)] = i
for i in range(1,N): 
    color = 0
    for j in V[i]:
        if j < i: 
            parent_color = Edict[(j,i)]
        else:
            if color == parent_color:
                color += 1
            Edict[(i,j)] = color
            color += 1
print(K)
for i in AB:
    print(Edict[i]+1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = i



stack = [(0, -1, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev, used = stack.pop()
    color = 0
    
    for v in nodes[u]:
        if v == prev:
            continue
        color += 1
        
        if color == used:
            color += 1
        a, b = min(u, v), max(u, v)
        i = edges[(a, b)]
        ans[i] = str(color)
        stack.append((v, u, color))
    
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(min(a,b),max(a,b))]=i
    ans=[None]*(n-1)

    def dfs(v=0,p=-1,c=0):
        col=1
        for nv in E[v]:
            col+=col==c
            if(nv==p): continue
            ans[idx[(min(v,nv),max(v,nv))]]=col
            dfs(nv,v,col)
            col+=1
    dfs()
    print(max(ans))
    print(*ans,sep='\n')
resolve()

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

Q = [(0, -1)]
ANS = [-1] * (N-1)
while Q:
    x, c0 = Q.pop()
    
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1

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

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


n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n-1)] 
graph = [[] for _ in range(n+1)]

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


root = 1
parent = [0] * (n+1) 
order = [] 
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1


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

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = i



stack = [(0, -1, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev, used = stack.pop()
    color = 0
    
    for v in nodes[u]:
        if v == prev:
            continue
        color += 1
        
        if color == used:
            color += 1
        a, b = min(u, v), max(u, v)
        i = edges[(a, b)]
        ans[i] = str(color)
        stack.append((v, u, color))
    
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        idx[(a,b)]=i
    ans=[None]*(n-1)

    
    Q=[(0,0)]
    while(Q):
        v,c=Q.pop()
        cnt=1
        for nv in E[v]:
            cnt+=cnt==c 
            ans[idx[(v,nv)]]=cnt
            Q.append((nv,cnt))
            cnt+=1

    print(max(ans))
    print(*ans,sep='\n')
resolve()

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


def main():
    N = int(input().strip())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().strip().split())
        edges[a-1].append([b-1, i])
        edges[b-1].append([a-1, i])
    color = [-1 for i in range(N-1)]
    trgt = deque([[0, -1], ])
    while len(trgt) > 0:
        now, parent_color = trgt.pop()
        cand_color = 0
        for node, edge_num in edges[now]:
            if color[edge_num] == -1:
                cand_color += 1
                if cand_color == parent_color:
                    cand_color += 1
                color[edge_num] = cand_color
                trgt.append([node, cand_color])
    print(max(color))
    print("\n".join(map(str, color)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N-1)]
Path=[[] for i in range(N)]
for p in P:
  Path[p[0]-1].append(p[1]-1)
  Path[p[1]-1].append(p[0]-1)
colornum=1
dic={}
def bfs(nodes,p,pcolor,selfnum):
  global colornum
  if len(nodes)-1==0 and p!=-1:
    return
  c=1
  for n in nodes:
    if n == p:
      continue
    if c==pcolor:
      c+=1
    dic[(selfnum+1,n+1)]=c
    dic[(n+1,selfnum+1)]=c
    bfs(Path[n],selfnum,c,n)
    c+=1
  if c>colornum:
    colornum=c
bfs(Path[0],-1,0,0)
print(colornum-1)
for p in P:
  print(dic[p])

Solution (Python):
from collections import  deque
import time
N = int(input())
dic = {}
A = [[int(j) for j in input().split()] for i in range(N - 1)]
for i in range(N - 1):
    a, b = A[i]
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic.keys():
        dic[b].append(a)
    else:
        dic[b] = [a]

ans1 = 0
for k, v in dic.items():
    ans1 = max(ans1, len(v))
no = 0
Used = [[] for i in range(N + 1)] 
q = deque()

q.append((1, dic[1], 1))
dicans = {}

while len(q) > 0:
    i, l, c= q.popleft()
    num = c
    for k in l:
        if k < i:
            continue
        num += 1
        if num > ans1:
            num = 1
        dicans[(i, k)] = num
        q.append((k, dic[k], num))

print(ans1)

for a, b in A:
    print(dicans[(a, b)])

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


def main():
    n = int(input())
    color = [None]*(n-1)
    color[0] = -1

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

    def dfs(now=0, prev=-1, mycolor=-1):
        in_use = {mycolor}
        i = 0

        for tup in con[now]:
            if tup[0] != prev:
                while True:
                    if i not in in_use:
                        color[tup[1]] = i
                        in_use.add(i)
                        break
                    i += 1
                dfs(tup[0], now, i)

    dfs()

    print(max(color)+1)
    for i in color:
        print(i+1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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


def bfs():
    q = deque()
    q.append((0, 0))

    while len(q):
        v, pc = q.popleft()
        color = 1

        for e in edge[v]:
            if color == pc:
                color += 1

            if ec[e[1]] == 0:
                ec[e[1]] = color
                q.append((e[0], color))
                color += 1


bfs()
print(max(ec))
for c in ec:
    print(c)

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

N=int(input())
Graph = [ [] for ii in range(N) ]

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

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

rec(0, 0)
print(max(ans))
print(*ans, sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
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(*ans, sep="\n")

Solution (Python):
n=int(input())
l=[[]for i in range(n)]
ans=set()
ll=[set() for i in range(n)]
c=1
ab=[]
from collections import Counter
ans2=Counter()
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    ab.append((a,b))
    l[a].append(b)
    

for i in range(n):
    c=1
    for j in l[i]:
        while True:
            if (c not in ll[j]) and (c not in ll[i]):
                ll[j].add(c)
                ll[i].add(c)
                ans.add(c)
                ans2[(i,j)]=c
                break
            else:
                c+=1
print(len(ans))


for i,j in ab:
    print(ans2[(i,j)])

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

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])

max_color = -1




queue = [1]




painted = {}


while queue:

    
    
    s = queue.pop(0)

    
    
    
    
    if s not in adj_dict:
        continue

    for i in range(len(adj_dict[s])):
        color = 1 + i
        if painted.get(s) is not None:
            if 0 < painted[s] <= color:
                color += 1
        
        painted[adj_dict[s][i]] = color
        max_color = max(max_color, color)
        queue.append(adj_dict[s][i])

print(max_color)

for edg in edge_list:
    print(painted[edg[1]])


'''
9
1 6
1 4
1 9
4 5
1 7
2 3
4 8
1 2

5
1
2
3
1
4
1
3
5
'''

Solution (Python):
import sys

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  

N = ni()
AB = [na() for _ in range(N-1)]
graph = [[] for _ in range(N+1)]

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
for o in order:
    ng = color[o]
    c = 1
    for y in graph[o]:
        if y == parent[o]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1
answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(answer))
print('\n'.join(map(str,answer)))

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

N = int(input())


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

ans = np.zeros(N - 1)


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


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

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


color_num = np.max(appeard)

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


color_queue = deque()


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

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

print(color_num)

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N=int(input())
val=[list(map(int, input().split())) for i in range(N-1)]

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[0]*(N-1)
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=1
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp
    coltemp+=1
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            coltemp=1
            que[i+1] |= arrtemp
            for f in arrtemp:
                while(1):
                    if coltemp not in col[t]:
                        break
                    coltemp+=1
                p=coltemp
                coltemp+=1
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])

Solution (Python):
def func(iro,tree,num,max_color):
  if num not in tree:
    return
  
  my_color = iro[num]
  arr = tree[num]
  
  for i in arr:
    my_color += 1
    iro[i] = my_color % max_color
    func(iro,tree,i,max_color)
    

n = int(input())
tree = {}

b_arr = []
for i in range(n-1):
  a,b = map(int,input().split())
  
  b_arr.append(b)
  if a not in tree:
    tree[a] = []
    
  tree[a].append(b)
  
color = len(tree[1])
for key,arr in sorted(tree.items()):
  if key == 1:
    continue
    
  color = max(len(arr)+1, color)

print(color)

iro = [-1] * (n+1)

for key,arr in sorted(tree.items()):
  my_color = iro[key]
  for i in arr:
    my_color += 1
    iro[i] = my_color % color

for i in b_arr:
  print(iro[i]+1)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []

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

ans = []

def dfs(v, fr, c):
    k = 1
    for g in G[v]:
        to = g.to
        id = g.id
        if to != fr:
            if k == c:
                k += 1
            ans[id] = k
            k += 1
            dfs(to, v, ans[id])
    

def main():
    global G, ans
    n = int(input().strip())
    ans = [0] * (n-1)
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = list(map(int, input().strip().split()))
        G[a-1].append(Edge(b-1, i))
        G[b-1].append(Edge(a-1, i))
    dfs(0, -1, -1)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        
    q = collections.deque([(0,1,0)])
    ans=dict()
    while q:
        parent,togo,old_color = q.popleft()
    
        col=1
        for togotogo in tree[togo-1]:
    
            if togotogo == parent:
                continue
            if col == old_color:
                col+=1
            q.append((togo,togotogo,col))
            ans["_".join(map(str,(togo,togotogo)))]=col
            col+=1
        
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s])
    
if __name__ == '__main__':
    main()

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

def main():
    n = int(readline())
    ab = map(int, read().split())
    ab = list(zip(ab, ab))
    g = [[] for _ in range(n+1)]
    for a, b in ab:
        g[a].append(b)
        g[b].append(a)

    parent = [0]*(n+1)
    color, maxc = [0]*(n+1), 0
    stack = [1]
    while stack:
        p = stack.pop()
        children = g[p]
        c, notc = 1, color[p]
        for child in children:
            if child==parent[p]:
                continue
            parent[child] = p
            stack.append(child)

            c = c+1 if c==notc else c
            color[child] = c
            maxc = c if maxc<c else maxc
            c+=1

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
e=[[] for _ in range(n)]
a=[0]*n
b=[0]*n
d={}
def dfs(x,last=-1,ban=-1):
    c=1
    for to in e[x]:
        if to==last:
            continue
        if c==ban:
            c+=1
        d[(x,to)]=c
        dfs(to,x,c)
        c+=1

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

dfs(0)
print(max(d.values()))
for i in range(n-1):
    if (a[i],b[i]) in d:
        print(d[(a[i],b[i])])
    else:
        print(d[(b[i],a[i])])

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

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[-1]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]<0:
            if visited[v]==j:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.append(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

Solution (Python):
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans = {}
tmp = []
flag = [False] * N  
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    tmp.append((a, b))  
    ans[(a, b)] = -1
q = deque([0])  
colors = [-1]*N
now_color = 0
while len(q):
    v = q.pop()
    flag[v] = True
    color = 1
    
    for e in graph[v]:

        if flag[e]:
            continue
        q.append(e)
        if color == colors[v]:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

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

G=[[] for _ in range(N+1)]
edge={}

for i in range(N-1):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    edge[(a,b)]=i
    edge[(b,a)]=i
que=deque()
que.append(1)
visited=[-1]*(N+1)
visited[1]=0
ans=[0]*(N-1)
while que:
    v=que.pop()
    j=1
    for u in G[v]:
        if visited[u]<0:
            if j==visited[v]:
                j+=1
            visited[u]=j
            ans[edge[(u,v)]]=j
            que.appendleft(u)
            j+=1
print(max(ans))
for a in ans:
    print(a)

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

N = int(input())

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

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

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

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

print(max(colors))
for c in colors:
    print(c)

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

N = int(input())

graph = [[] for i in range(N)]

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

ans = [0] * (N - 1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1


dfs(-1, 1, -1)

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

Solution (Python):
from collections import defaultdict
N = int(input())
tree = [[] for i in range(N)]  
degrees = defaultdict(int)  

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



ans_K = max(degrees.values())
ans_c = [-1] * (N - 1)



stack = [[0, -1]]
visited = [False] * N
while stack:
    fr, pre_color = stack.pop()
    visited[fr] = True
    painting = 1  

    for to, index in tree[fr]:
        if visited[to]:
            continue

        if painting == pre_color:
            painting += 1

        ans_c[index] = painting
        stack.append([to, painting])

        
        painting += 1


print(ans_K)
print(*ans_c, sep='\n')

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

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

parent = [0]*(n+1)
stack = [1]
while stack:
	v = stack.pop()
	for c in tree[v]:
		if c == parent[v]:
			continue
		parent[c] = v
		stack.append(c)

color = [0]*(n+1)
for i in range(1,n+1):
	cur_col = 1
	par_col = color[i]
	for c in tree[i]:
		if c == parent[i]:
			continue
		if cur_col == par_col:
			cur_col += 1
		color[c] = cur_col
		cur_col += 1
	

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