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**8)
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]

path=[[] for _ in range(n)]
for i,(a,b) in enumerate(AB):
  a,b=a-1,b-1
  path[a].append((b,i))
  path[b].append((a,i))
  
visited=[0]*n
ans=[None]*(n-1)
  
def dfs(v,c=-1):
  nc=1
  for to,i in path[v]:
    if visited[to]: continue
    visited[v]=1
    if nc==c: nc+=1
    ans[i]=nc
    dfs(to,nc)
    nc+=1
dfs(0)
print(max(ans))
print(*ans,sep='\n')

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

input = sys.stdin.readline
n = int(input())
G = [[] for _ in range(n)]
E = []
for i in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    E.append((a, b))

cs = []
ans = {}
def dfs(v, p, c):
    color = 0
    for g in G[v]:
        if g == p:
            continue
        color += 1
        if color == c:
            color += 1
        dfs(g, v, color)
        ans[(v+1, g+1)] = color

dfs(0, -1, 0)
print(max(ans.values()))
for e in E:
    print(ans[e])

Solution (Python):
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

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

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

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

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

N = int(input())


class Node:
    def __init__(self, index):
        self.index = index
        self.edges = []

class Edge:
    def __init__(self, index, a, b):
        self.a = a
        self.b = b
        self.index = index
        self.color = 0

    def to(self, fm):
        if fm == self.a:
            return self.b
        elif fm == self.b:
            return self.a
        else:
            return None


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

passed = set()


def rec(node, via_color, K):
    passed.add(node.index)
    color = 1
    for edge_index in node.edges:
        edge = edges[edge_index]
        to_node_index = edge.to(node.index)
        if to_node_index in passed:
            continue
        if color == via_color:
            color += 1
        edge.color = color
        K = rec(nodes[to_node_index], color, K)
        color += 1
    return max(color-1, K)


K = rec(nodes[0], 0, 1)
print(K)
for edge in edges:
    print(edge.color)

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

N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for b,i in E[p]:
    if m == n: m+=1
    ans[i]=m
    sub(b,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

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

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

es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append((b, i))
    es[b].append((a, i))

visited = [0]*n
ans_color = [0]*(n-1)


def dfs(v, fromColor):
    color = 1
    visited[v] = 1
    for to, i in es[v]:
        if visited[to]: continue

        if color == fromColor:
            color += 1
        ans_color[i] = color
        dfs(to, color)
        color += 1

root = 0 
dfs(root, 0)

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

Solution (Python):
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])

Solution (Python):
from collections import deque

import sys
sys.setrecursionlimit(10**6)

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


root = 1
nodes[root][0] = root
for i in range(N-1):
    a,b = AB[i]
    nodes[a][1].append(b)
    nodes[b][0] = a


K = len(nodes[1][1])

for i in range(2,N+1):
    K = max(K,len(nodes[i][1])+1)

Q = deque([root])

while len(Q) != 0:
    q = Q.popleft()
    children = nodes[q][1]
    root_color = nodes[q][2]
    i = 1
    for child in children:
        Q.append(child)
        if i == root_color:
            i += 1
        nodes[child][2] = i
        i += 1


print(K)
for a,b in AB:
    print(nodes[b][2])

Solution (Python):
N = int(input())
e = []
ed = {}
g = [[] for i in range(N)]
c = [0]*(N-1)
ny = [0]*N
for i in range(N-1):
    a, b = (int(i) for i in input().split())
    ny[a-1] += 1
    ny[b-1] += 1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    e.append((a-1,b-1))
    ed[(a-1, b-1)] = i

mac = max(ny)
for i in range(N):
    if ny[i] == mac:
        oya = i
        break

Q = [(0, oya)]
prev = [False]*N
while Q:
    col, v = Q.pop()
    prev[v] = True
    l = g[v]
    ucol = 0
    for u in l:
        if not prev[u]:
            ucol += 1
            if col == ucol:
                ucol += 1
            Q.append((ucol, u))
            a, b = min(u, v), max(u, v)
            c[ed[(a, b)]] = ucol
print(mac)
for i in range(N-1):
    print(c[i])

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

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

adj = defaultdict(list)
for i, (a, b) in enumerate(ab):
	a -= 1
	b -= 1
	adj[a].append((b, i))
	adj[b].append((a, i))

k = max([len(li) for li in adj.values()])
print(k)

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

def dfs(u, p_col):
	col = 1
	for v, i in adj[u]:
		if ans[i] != -1:
			continue
		if col == p_col:
			col += 1
		ans[i] = col
		dfs(v, col)
		col += 1


dfs(0, -1)

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

Solution (Python):
from collections import deque

def enable_color(vertex, color_count, used_color):
    used = used_color[vertex]
    for i in range(1, color_count+1):
        if i not in used:
            return i

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

    leafs = [[] for _ in range(N+1)]
    for a, b in AB:
        leafs[a].append(b)

    
    q = deque()
    q.append(1)
    color = [0] * (N + 1)

    while q:
        root = q.popleft()
        used_color = color[root]
        c = 1
        for leaf in leafs[root]:
            if c == used_color:
                c += 1
            color[leaf] = c
            c += 1
            q.append(leaf)
    print(max(color))
    for _, b in AB:
        print(color[b])


if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque

N = int(input())

graph = [[] for _ in range(N + 1)]
seq = []

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



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

while q:
    checking_parent = q.popleft()
    parent_color = color[checking_parent]
    c = 1
    for child in graph[checking_parent]:
        if c == parent_color:
            c += 1
        
        color[child] = c
        c += 1
        
        q.append(child)

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

Solution (Python):
import sys
from collections import defaultdict, deque

readline = sys.stdin.readline
n = int(readline())
ab = [None] * (n-1)
G = [list() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    ab[i] = a, b
colors = defaultdict(int)
q = deque([0])
used = [0] * n
used[0] = 10**6
K = 0
while q:
    x = q.popleft()
    c = 1
    for y in G[x]:
        if used[y]:
            continue
        if used[x] == c:
            c += 1
        used[y] = colors[x, y] = colors[y, x] = c
        c += 1
        q.append(y)

print(max(colors.values()))
print('\n'.join(str(colors[i]) for i in ab))

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

def main():
    N = int(input())
    e = []
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        e.append(b)
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    col = 0
    for x in edge:
        col = max(col,len(x))
        
    print(col)
    ans = [-1 for _ in range(N)]
    go = [False for _ in range(N)]
    q = deque([0])
    while q:
        now = q.pop()
        go[now] = True
        c = 0
        for fol in edge[now]:
            if go[fol]:
                continue
            if c != ans[now]:
                ans[fol] = c
            else:
                ans[fol] = col-1
            c += 1
            q.append(fol)
    
    for i in range(N-1):
        print(ans[e[i]-1]+1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

que=deque([0])
while que:
   s=que.pop()
   color=1
   for ni in G[s]:
      if ans[s]==color:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Solution (Python):

import heapq
import collections
from collections import deque

n = int(input())
ab = []
visit = [-1 for _ in range(n+1)]
tree = [[]  for _ in range(n+1)]
colors = {}
for i in range(n-1):
    a, b = map(int,input().split())
    ab.append((a, b))
    tree[a].append(b)
    tree[b].append(a)
    colors[(a,b)] = -1
    colors[(b,a)] = -1


visit[1]=1

q = deque([(1,0)]) 
K = 0
while q:
    v,from_color = q.popleft()
    c = 1
    for next_v in tree[v]:
        if visit[next_v] == -1:
            visit[next_v] = 1
            if c == from_color:
               c += 1
            colors[(v,next_v)] = colors[(next_v,v)] = c
            q.append((next_v,c))
            c += 1
anss = []
K = 0
for temp in ab:
    a,b = temp
    K = max(K, colors[(a,b)] )
    anss.append(colors[(a,b)])

print(K)
for c in anss:
    print(c)

Solution (Python):
from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()

Solution (Python):
from collections import deque, defaultdict

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


outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: 
        count += 1
        if dicthoji[v1] == count: 
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])


print(max(dicthoji.values()))
for i in range(N-1):
    print(dicthoji[ab[i][1]])

Solution (Python):
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    ans = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()
            cnt=1

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if ans[x]!=cnt:
                        ans[y]=cnt
                        cnt+=1
                    else:
                        cnt+=1
                        ans[y]=cnt
                        cnt+=1

        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)

x=tree(0)
print(max(x))
for i in range(n-1):
    print(x[a[i][1]-1])

Solution (Python):
from collections import deque, defaultdict

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


outs = defaultdict(list)
ins = defaultdict(int)

for v1, v2 in ab:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(1,N+1) if ins[v1] == 0)
hoji = []
dicthoji = {1: 0}

while q:
    v1 = q.popleft()
    count = 0
    for v2 in outs[v1]: 
        count += 1
        if dicthoji[v1] == count: 
            count += 1
        ins[v2] -= 1
        q.append(v2)
        dicthoji.update([(v2,count)])
        hoji.append(count)


print(max(hoji))
for i in range(N-1):
    print(dicthoji[ab[i][1]])

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


def Treemake(node,parent,root,num):
    A.append([node,parent,root,num])
    for i,j in root:
        Treemake(i,node,Tree[i],j)


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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextV  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextV.append(b)
    
q = deque([1]) 
color = [0]*(N+1)
while q:
  v = q.popleft()
  parentC = color[v]
  c = 1
  for child in graph[v]:
    if c == parentC: 
      c += 1
    color[child] = c 
    c += 1 
    q.append(child)
    
print(max(color))    
for b in nextV:
  print(color[b])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextEdege  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextEdege.append(b)
  
q = deque([1]) 
color = [0]*(N+1)
while q:
  v = q.popleft()
  c = 1
  for u in graph[v]:
    if c == color[v]:
      c += 1
    color[u] = c
    c += 1
    q.append(u)
    
print(max(color))    
for b in nextEdege:
  print(color[b])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)

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


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    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
        ans[j[1]]=i+1+flag

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

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


def rootedTree(node,parent,root,num):
    A.append([node,parent,root,num])
    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
        ans[j[1]]=i+1+flag

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

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

class Node:
    def __init__(self, id_=0):
        self.id = id_
        self.link = []
        self.edge_ids = []
        self.check = False

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

    nodes = [Node(i) for i in range(N+1)]
    for i, (a, b) in enumerate(ab):
        nodes[a].link.append(nodes[b])
        nodes[a].edge_ids.append(i)
        nodes[b].link.append(nodes[a])
        nodes[b].edge_ids.append(i)
    
    ans = 0
    edge_colors = [0 for i in range(N-1)]

    q = deque()
    
    q.append((nodes[1], 0))
    nodes[1].check = True

    while len(q) > 0:
        node, pre_color = q.popleft()
        
        next_color = 1
        for next_node, edge_id in zip(node.link, node.edge_ids):
            if not next_node.check:
                
                if next_color == pre_color:
                    next_color += 1
                ans = max(ans, next_color)
                edge_colors[edge_id] = next_color
                q.append((next_node, next_color))
                next_node.check = True
                next_color += 1
    
    print(ans)
    for color in edge_colors:
        print(color)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))
ans=[0]*(N-1)
g=[0]*N
def dfs(v,h=-1):
  res=1
  for i,j in es[v]:
      if g[i]:
            continue
      g[v]=1
      if h==res:
            res+=1
      ans[j]=res
      dfs(i,res)
      res+=1

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

Solution (Python):
from collections import deque

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

que=deque([0])
while que:
   s=que.pop()
   color=1
   for ni in G[s]:
      if ans[s]==color:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Solution (Python):
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])

Solution (Python):
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.popleft()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for ni in L:
   print(ans[ni])

Solution (Python):
from collections import deque

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

que=deque([0])
ans=[0]*n
while que:
   s=que.pop()
   color=1
   for ni in E[s]:
      if color==ans[s]:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for ni in L:
   print(ans[ni])

Solution (Python):
from collections import deque

n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	a, b = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
 
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
 
print(max(ans))
for node in node_list:
	print(ans[node])

Solution (Python):



def main():
    
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 7)

    n = int(input())
    graph = [list() for _ in range(n)]
    ans = [0 for _ in range(n - 1)]

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

    
    
    

    
    def dfs(vertex, parent=-1, edge_color=-1):
        
        color_code = 1

        
        for to, edge_id in graph[vertex]:
            if to == parent:
                continue

            
            if color_code == edge_color:
                color_code += 1

            ans[edge_id] = color_code
            color_code += 1

            dfs(to, vertex, ans[edge_id])
            

        

    dfs(0)
    count = 0

    for g in graph:
        count = max(count, len(g))

    print(count)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 7)

    n = int(input())
    graph = [list() for _ in range(n)]
    ans = [0 for _ in range(n - 1)]

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

    def dfs(vertex, parent=-1, edge_color=-1):
        color_code = 1

        for to, edge_id in graph[vertex]:
            if to == parent:
                continue

            if color_code == edge_color:
                color_code += 1

            ans[edge_id] = color_code
            color_code += 1

            dfs(to, vertex, ans[edge_id])

    dfs(0)
    count = 0

    for g in graph:
        count = max(count, len(g))

    print(count)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 7)

    n = int(input())
    graph = [list() for _ in range(n)]
    ans = [0 for _ in range(n - 1)]

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

    def dfs(vertex, parent=-1, edge_color=-1):
        color_code = 1

        for to, edge_id in graph[vertex]:
            if to == parent:
                continue

            if color_code == edge_color:
                color_code += 1

            ans[edge_id] = color_code
            color_code += 1

            dfs(to, vertex, ans[edge_id])

    dfs(0)
    count = 0

    for g in graph:
        count = max(count, len(g))

    print(count)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class Edge:
    def __init__(self, first, second):
        self.color = 0
        self.first = first
        self.second = second

def main():
    def dfs(i, par, pcol):
        cc = 1
        for e in v[i]:
            if cc == pcol:
                cc += 1
            if e.color == 0:
                e.color = cc
                dfs(e.second, par, cc)
                cc += 1

    n = int(input())
    e = [[] for _ in range(n-1)]
    v = [[] for _ in range(n+1)]

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

    dfs(1, -1, 0)

    m = 0
    for i in range(n-1):
        m = max(m,e[i].color)

    print(m)
    for i in range(n-1):
        print(e[i].color)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
 
N = int(input())
edges = [[] for _ in range(N + 1)]
ends = []
 
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    ends.append(b)
 
nodes = deque([1])
count = [0] * (N + 1)
 
while nodes:
    node = nodes.popleft()
    nodes.extend(edges[node])
 
    c = 0
    for n in edges[node]:
        c += 1 + (c + 1 == count[node])
        count[n] = c
 
print(max(count))
for i in ends:
    print(count[i])

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

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

    K = 0
    for i in range(N):
        K = max(K, len(edges[i]))

    visited = [False] * N

    def dfs(v, color):
        visited[v] = True
        for l, m in enumerate(edges[v]):
            if visited[m[0]]:
                continue
            color += 1
            color %= K
            ans.append((m[1],color))
            dfs(m[0], color)

    dfs(0,0)

    ans.sort()
    print(K)
    for a, b in ans:
        print(b+1)

if __name__ == "__main__":
    main()

Solution (Python):
import collections
from collections import deque
def clear_maze(s):

    INF=-10**9
    ans = [INF for i in range(n)]
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            v=1
            x = d.popleft()
            for i in range(len(b[x])):
                y=b[x][i]
                if ans[y] == INF:
                    d.append(y)
                    if ans[x]==v:
                        v+=1
                    ans[y]=v
                    v+=1
        return ans
    return bfs()

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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)


c=clear_maze(0)
print(max(c))
for i in range(n-1):
    print(c[a[i][1]-1])

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

n=int(input())
l=[[] for i in range(n)]
ans=[0]*(n-1)

def dfs(v,c,p):
  k=1
  for i in range(len(l[v])):
    u=l[v][i][0]
    id=l[v][i][1]
    if(u==p):continue
    if(k==c):k+=1
    ans[id]=k
    dfs(u,ans[id],v)
    k+=1
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append((b-1,i))
  l[b-1].append((a-1,i))
dfs(0,-1,-1)
print(max(ans))
for i in ans:
  print(i)

Solution (Python):
from collections import deque
N = int(input())
node_dic = {}
ab_array = [list(map(int,input().split())) for _ in range(N-1)]

for a,b in ab_array:
    if a in node_dic:
        node_dic[a][b] = 0
    else:
        node_dic[a] = {b : 0}
    if b in node_dic:
        node_dic[b][a] = 0
    else:
        node_dic[b] = {a : 0}



max_color = 0

queue = deque()
flag = [0] * N
first = ab_array[0][0]
queue.append((first,0))
flag[first-1] = 1

while len(queue):
    p, ban_color = queue.popleft()
    now_color = 1
    for key in node_dic[p].keys():
        if now_color == ban_color:
            now_color += 1
        if flag[key-1] == 0:
            queue.append((key,now_color))
            node_dic[p][key] = now_color
            node_dic[key][p] = now_color
            flag[key-1] = 1
            max_color = max(max_color,now_color)
            now_color += 1
print(max_color)
for a,b in ab_array:
    print(node_dic[a][b])

Solution (Python):
from collections import OrderedDict
from collections import deque
N = int(input())
G = [[] for _ in range(N)]
od = OrderedDict()

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

used = [False]*N 
parent2colors = [0]*N 
que = deque()
que.append(0)
used[0] = True
colors = 0

while len(que) != 0:
    v = que.popleft()
    colors = max(colors,len(G[v]))
    cur_color = 1
    for nv in G[v]:
        if used[nv]:continue 
        if cur_color == parent2colors[v]:
            cur_color += 1

        if (v,nv) in od.keys():
            od[(v,nv)] = cur_color
        else:
            od[(nv,v)] = cur_color
        parent2colors[nv] = cur_color
        cur_color += 1
        used[nv] = True
        que.append(nv)

print(colors)
for edge_clr in od.values():
    print(edge_clr)

Solution (Python):
import copy ; import sys ; sys.setrecursionlimit(11451419)
n=int(input())
HEN=[list(map(int,input().split())) for _ in range(n-1)]
G=[[] for _ in range(n)]
for i,[a,b] in enumerate(HEN):
    a=a-1;b=b-1
    G[a].append([b,i])
    G[b].append([a,i])  

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

def search(v,c=-1):  
    nc=1
    for to,i in G[v]:
        if visited[to]==1: continue
        visited[v]=1
        if c==nc:
            nc+=1
        ans[i]=nc
        search(to,nc)
        nc+=1
search(0)
print(max(ans))
print(*ans,sep="\n")