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



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    N = int(input())
    # path = [[] for _ in range(N)]
    path = [[] for _ in range(N-1)]
    ab = []
    ans = {}
    visited = [False] * N
    visited[0] = True
    for _ in range(N-1):
        a, b = map(int, input().split())
        path[a-1].append(b-1)
        # path[b-1].append(a-1)
        ab.append((a-1, b-1))
    
    que = deque([(0, 0)])
    while que:
        k = 1
        pre, c = que.popleft()
        for next_node in path[pre]:
            if visited[next_node]:
                continue
            
            if c == k:
                k += 1
            visited[next_node] = True
            ans[(pre, next_node)] = k
            que.append((next_node, k))
            k += 1
            

    print(max(ans.values()))
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    ab = []
    ans = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
        ab.append(str(a-1)+str(b-1))
    
    K = max([len(g) for g in edges])
    init = [[0, node, i+1] for i, node in enumerate(edges[0])]  # [parent, current, color]
    que = deque(init)
    for _, _, i in init:
        ans['0'+str(i)] = i
    while que:
        c = 1
        p, node, color = que.popleft()
        next_nodes = edges[node]        
        for next_node in next_nodes:
            if next_node == p:
                continue
            if c == color:
                c += 1
            ans[str(node)+str(next_node)] = c
            que.append([node, next_node, c])
            c += 1

    print(K)
    for key in ab:
        print(ans[key])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
    
    K = max([len(g) for g in edges[1:]])
    K = max(K+1, len(edges[0]))
    init = [[node, i+1] for i, node in enumerate(edges[0])]
    que = deque(init)
    colors = set([i for i in range(1, K+1)])
    ans = [i for n, i in init]
    while que:
        node, color = que.popleft()
        if node >= N-1:
            continue

        next_nodes = edges[node]
        next_colors = list(colors - set([color]))
        
        for i in range(len(next_nodes)):
            ans.append(next_colors[i])
            que.append([next_nodes[i], next_colors[i]])

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    N = int(input())
    edges = [[] for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
    
    K = max([len(g) for g in edges[1:]])
    K = max(K+1, len(edges[0]))
    init = [[node, i+1] for i, node in enumerate(sorted(edges[0]))]
    que = deque(init)
    colors = set([i for i in range(1, K+1)])
    ans = [i for n, i in init]
    while que:
        node, color = que.popleft()
        if node >= N-1:
            continue

        next_nodes = edges[node]
        next_nodes.sort()
        next_colors = list(colors - set([color]))
        
        for i in range(len(next_nodes)):
            ans.append(next_colors[i])
            que.append([next_nodes[i], next_colors[i]])

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import queue
N=int(input())
A=[]
B=[]
dic={}
for i in range(N-1):
  a,b=map(int,input().split())
  A+=[a]
  B+=[b]
  dic[(a,b)]=i
  dic[(b,a)]=i
vote=[[] for i in range(N)]#それぞれの頂点につながる辺のリスト
for i in range(N-1):
  vote[A[i]-1]+=[i+1]
  vote[B[i]-1]+=[i+1]
maxi=0
K=0
for i in range(N):
  if len(vote[i])>K:
    K=len(vote[i])
    maxi=i
print(K)
candq=queue.Queue()
candq.put(maxi)
zumi=[]
colorl=[[i for i in range(K)] for i in range(N)]
color=[0 for i in range(N-1)]
while not candq.empty():
  a=candq.get() #頂点の番号（文章中の値より１小さい）
  zumi+=[a]
  nextl=vote[a]
  for i in nextl:
    if i in zumi:
      continue
    else:
      brunch=dic[(a,i)]
      c=min(colorl[brunch])
      color[brunch]=c
      colorl[brunch].remove(c)
      candq.put(i)
    
for i in color:
  print(i+1)

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
#%%
e = [[] for i in range(N)]
k = [0 for i in range(N)]
for a, b in ab:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
#%%
ans = [k for i in range(N)]
max_e = 0
for e_ in e:
    max_e = max(max_e, len(e_))
print(max_e)

def dfs(s=0,p=-1,pe=-1):
    ts = e[s]
    e_num=1
    for t in ts:
        if t==p:
            continue
        if e_num==pe:
            e_num+=1
        ans[s][t] = e_num
        ans[t][s] = e_num
        dfs(s=t, p=s, pe=e_num)
        e_num +=1

dfs()
for a, b in ab:
    print(ans[a-1][b-1])

Submission status: Runtime Error

Solution code:
N = int(input())
#%%
e = [[] for i in range(N)]
import numpy as np
ans = np.empty((N,N), dtype=np.int)

ab = [list(map(int, input().split())) for i in range(N-1)]
for a, b in ab:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
#%%
ans = np.empty((N,N), dtype=np.int)
max_e = 0
for e_ in e:
    max_e = max(max_e, len(e_))
print(max_e)

def dfs(s=0,p=-1,pe=-1):
    ts = e[s]
    e_num=1
    for t in ts:
        if t==p:
            continue
        if e_num==pe:
            e_num+=1
        ans[s][t] = e_num
        ans[t][s] = e_num
        dfs(s=t, p=s, pe=e_num)
        e_num +=1

dfs()
for a, b in ab:
    print(ans[a-1][b-1])


#%%

Submission status: Runtime Error

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari ={}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])

# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え

#
color_set =set("")
#頂点とつながり先をキー、色をValueの辞書
color_ten_ten = {}
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_set =set([i for i in range(1,color_max+1) ])
    for ii in v:
        if (col_sumi[k] & color_set) and (k<ii) :
            color_set = color_set - col_sumi[k] # 今の頂点に対して覚えていた色を消す
        if (col_sumi[ii] & color_set) and (k<ii):    
            color_set =color_set - col_sumi[ii] # 先の頂点に対して覚えていた色を消す
        if k<ii:
            xx = color_set.pop() # ポップだから速度のため末尾から消す  
            color_ten_ten.setdefault((k,ii) ,xx)  
        #else:
            #xx = color_set.pop() # ポップだから速度のため末尾から消す  
            #color_ten_ten.setdefault((ii,k) ,xx)  
        col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
        col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

Submission status: Runtime Error

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari ={}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])

# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え

#
#color_set =[i for i in range(1,color_max+1)]
color_set =set("")
#頂点とつながり先をキー、色をValueの辞書
#color_moto ={i:color_set for i in tunagari.keys()} #元は１こだけ
color_ten_ten = {}
col =[] #　色の一時的な変数
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_set =set([i for i in range(1,color_max+1) ])
    for ii in v:
        if (col_sumi[k] & color_set) and (k<ii) :
            color_set = color_set - col_sumi[k] # 今の頂点に対して覚えていた色を消す
        if (col_sumi[ii] & color_set) and (k<ii):    
            color_set =color_set - col_sumi[ii] # 先の頂点に対して覚えていた色を消す
        if k<ii:
            xx = color_set.pop() # ポップだから速度のため末尾から消す  
            color_ten_ten.setdefault((k,ii) ,xx)  
        else:
            color_ten_ten.setdefault((ii,k) ,xx)  
        col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
        col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import floor

a, b, x = map(int, readline().split())
memo = floor(x / a) - 1
if memo >= 10 ** 9:
    print(10 ** 9)
    exit()
elif memo < 0:
    print(0)
    exit()
dg = len(str(memo))
for i in range(memo + 10 ** 5, 0, -1):
    if x - a * i >= b * dg:
        print(i)
        exit()
print(0)

Submission status: Runtime Error

Solution code:
from collections import deque

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


color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    k = 0
    c = 1
    r = q.popleft()
    m = T[r][0]
    if r > m:
        k = color[r][m]
        T[r].remove(m)
    for j in T[r]:
        if c != k:
            color[r][j] = c
            color[j][r] = c
        else:
            c += 1
            color[r][j] = c
            color[j][r] = c
        c += 1
        q.append(j)
    total = max(total,c-1)

print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Runtime Error

Solution code:
N=int(input())

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)

print(max(L))
for l in L:
  print(l)

Submission status: Runtime Error

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)
"""
print(max(L))
for l in L:
  print(l)
"""

Submission status: Runtime Error

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)
print(max(L))
for l in L:
  print(l)

Submission status: Runtime Error

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node, L):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node, L)
    col+=1
  return

dfs(0,-1,-1,L)
print(max(L))
for l in L:
  print(l)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[]
count=[0]*N

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

cs=[ 2**ans_1-1 ]*N

for each in edges:
    e1,e2=each
    cand=list(range(ans_1))
    ands=str(bin(cs[e1]&cs[e2]))[2:].zfill(ans_1)
    cc=ands.index("1")
    cs[e1]-=2**(ans_1-cc-1)
    cs[e2]-=2**(ans_1-cc-1)

    print(cc+1)

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[]
count=[0]*N

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

cs=[ 2**ans_1-1 ]*N

for each in edges:
    e1,e2=each
    cand=list(range(ans_1))
    ands=str(bin(cs[e1]&cs[e2]))[2:].zfill(ans_1)
    cc=ands.index("1")
    cs[e1]-=2**(ans_1-cc-1)
    cs[e2]-=2**(ans_1-cc-1)

    print(cc)

Submission status: Runtime Error

Solution code:
n=int(input())
L=[[] for i in range(n)]
V=[]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
    V.append([a,b])
k=max(len(l) for l in L)
C=[-1]*n
D=[-1]*n
def dfs(s,p=-1,d=0): #深さ優先探索(親,上の辺の色,深さ)
    c=C[s]
    for i in L[s]: #子に対して
        if i!=p: #親と一緒じゃないとき
            c=(c+1)%k
            C[i]=c
            D[i]=d
            dfs(i,s,d+1) #色をつけ、スタートを更新し、再探索

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

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[]
count=[0]*N

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

ans_1=max(count)
colors=[-1]*(N-1)
c_list=[tuple(range(ans_1))]*N

while True:
    if len(edges)==0:
        break
    edge=edges.pop(0)
    e1,e2=edge[1],edge[2]

    for ee in c_list[e1]:
        if ee in c_list[e2]:
            cc=ee
            break

    z1=list(c_list[e1])
    z1.remove(cc)
    c_list[e1]=tuple(z1)
    z2=list(c_list[e2])
    z2.remove(cc)
    c_list[e2]=tuple(z2)
    colors[edge[0]]=cc

print(ans_1)
for i in range(N-1):
    print(colors[i]+1)

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

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

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

Submission status: Runtime Error

Solution code:
N = int(input())

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


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

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

Submission status: Runtime Error

Solution code:
N=int(input())
S=[[] for _ in range(N-1)]

for i in range(N-1):
  a, b=map(int, input().split())
  S[a-1].append(b-1)
  S[b-1].append(a-1)
  
def dfs(start, pre, pre_col, S, ans):
  col=1
  for i, nex in enumerate(S[start-1]):
    if nex==pre:
      continue
    if col=pre_col:
      col+=1
    ans[nex]=col
    dfs(nex, start, col, S, ans)
    col+=1
    
ans=[0]*(N-1)
dfs(1, -1,-1,S, ans)
print(max(ans))
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    ans = [-1] * (N-1)
    def dfs(i, color):
        if i == N:
            return
        ans[i-1] = color

        c = 1
        for g in graph[i]:
            if c == color:
                c += 1
            dfs(g, c)
            c += 1

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
abi = [[] for _ in range(n+1)]
ans = [0] * (n-1)
for i,(a,b) in enumerate(ab):
    abi[a].append((i,b))
    abi[b].append((i,a))

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

dfs(1)

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

Submission status: Runtime Error

Solution code:
G = None
ans = None

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

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

main()

Submission status: Runtime Error

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


# print(ki)


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


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

Submission status: Runtime Error

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

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

dfs()

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
branch_list = defaultdict(list)
branch_index_map = {}
for i in range(N-1):
    a, b = map(int, input().split())
    branch_list[a].append(b)
    branch_list[b].append(a)
    branch_index_map[(a,b)] = i
    branch_index_map[(b,a)] = i

K = max(map(len, branch_list.values()))

done_flag = [0] * N
color_map = [None] * (N-1)

def draw_from(ni):
    done_flag[ni-1] = 1
    color_set = set()
    for sub_ni in branch_list[ni]:
        bi = branch_index_map[(ni, sub_ni)]
        if color_map[bi] is not None:
            color_set.add(color_map[bi])

    for sub_ni in branch_list[ni]:
        bi = branch_index_map[(ni, sub_ni)]
        if color_map[bi] is None:
            for c in range(1, K+1):
                if c not in color_set:
                    color_map[bi] = c
                    color_set.add(c)
                    break
   
    for sub_ni in branch_list[ni]:
        bi = branch_index_map[(ni, sub_ni)]
        if done_flag[sub_ni-1] == 0:
            draw_from(sub_ni)

print(K)

draw_from(1)
for c in color_map:
    print(c)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

N = int(input())

color = [[] for _ in range(N)]
ans = [None]*(N-1)


for i in range(N):
    heapq.heapify(color[i])

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

    else:
        if color[a-1]:
            if color[a-1][0] != 1:
                mim = heapq.heappop(color[a-1])
                heapq.heappush(color[a-1],mim)
                heapq.heappush(color[a-1],mim-1)
                heapq.heappush(color[b-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[a-1][-1]
                heapq.heappush(color[a-1],nax+1)
                heapq.heappush(color[b-1],nax+1)
                ans[i] = nax+1
        else:
            if color[b-1][0]!= 1:
                mim = heapq.heappop(color[b-1])
                heapq.heappush(color[b-1],mim)
                heapq.heappush(color[b-1],mim-1)
                heapq.heappush(color[a-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[b-1][-1]
                heapq.heappush(color[b-1],nax+1)
                heapq.heappush(color[a-1],nax+1)
                ans[i] = nax+1

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

#print(adj)

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

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(N-1,0)

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

Submission status: Runtime Error

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

#print(adj)

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

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(2,0)

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

Submission status: Runtime Error

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

#print(adj)

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

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(1,0)

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

Submission status: Runtime Error

Solution code:

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

#print(adj)

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

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==True:
      continue
    #if edge_color[e] == 0:
    #print(col_lis)
    edge_color[f] = col_lis.pop(0)
    dfs(w,f)
  return None
#print(col_num)
dfs(1,0)

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

Submission status: Runtime Error

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

#print(adj)

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

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  #print(col_lis)
  if len(adj[v])==0:
    return None
  for w,e in adj[v]:
    if visited[w]==True:
      continue
    #if edge_color[e] == 0:
    edge_color[e] = col_lis.pop(0)
    dfs(w,e)
  return None
#print(col_num)
dfs(1,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
Mat = [[] for _ in range(N)]
for i in range(N-1):
    a,b = list(map(int, input().split(' ')))
    a,b = a-1,b-1
    Mat[a].append([i,b])
    Mat[b].append([i,a])
    
colL = [1 for i in range(N-1)]
colorSave = []
 
M = 0
for i in range(N):
    if M < len(Mat[i]):
        M = len(Mat[i])
print(M)
def bfs(now,bef,nowC,befC,first):
    colL = [1 for i in range(N-1)]
    if first == 0:
        colL[nowC] = 0
    for nex in Mat[now]:
        if nex[1] != bef:
            nexC = colL.index(1)
            colL[nexC] = 0
            colorSave.append([nex[0],nexC])
            bfs(nex[1],now,nexC,nowC,0) 
    return

bfs(0,-1,0,-1,1)
new = sorted(colorSave,key=lambda x:x[0])
for n in new:
    print(n[1]+1)

Submission status: Runtime Error

Solution code:

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

colL = [1 for i in range(N-1)]
colorSave = []
    
def bfs(now,bef,nowC,befC,first):
    colL = [1 for i in range(N-1)]
    if first == 0:
        colL[nowC] = 0
    for nex in Mat[now]:
        if nex[1] != bef:
            nexC = colL.index(1)
            colL[nexC] = 0
            colorSave.append([nex[0],nexC])
            bfs(nex[1],now,nexC,nowC,0) 
    return

bfs(0,-1,0,-1,1)
new = sorted(colorSave,key=lambda x:x[0])
new2 = sorted(colorSave,key=lambda x:x[1])
print(new2[-1][1]+1)
for n in new:
    print(n[1]+1)