Problem p02850 (python)

Fixed submission:
"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

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

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')

Buggy submission (verdict: Runtime Error):
    #初期入力
    import sys
    input = sys.stdin.readline
    import heapq
    N = int(input())
    connection   ={i:set() for i in range(1,N+1)}
    A            =[i for i in range(N-1)]
    for i in range(N-1):
        a,b = (int(x) for x in input().split())
        connection[a].add(b) # つながりを逆向きも含めて入力
        connection[b].add(a) # 
        A[i] =a,b            #色を出力するため
     
    #色の数(各頂点の最大値)
    color_max =0
    root =0
    for i,v in connection.items():
        if color_max < len(v) :
            color_max =len(v)
            root =i         #枝が一番多い所を根 ⇒スタート
     
    #各頂点に色を準備⇒辺の色決定
    aa=[]
    color =0                                 #辺に塗る色の候補
    node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
    edge ={}
    for a,b in A:
        edge[(a,b)] =-1                   #辺の色 -1で初期化
    now_set =set() #=start
    now_set.add(root) #=start
    next =set()
    next_next =set()
    passed ={i:False for i in range(1,N+1)}
    count =0
    while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
        for now in now_set: #幅優先探索
            next =connection[now]
            for nex_2 in next:
                count =0
                if node[now] !=[]:
                    color =node[now][-1] +1
                while count < color_max:
                    q,color =divmod(color,color_max)
                    if color not in node[now] and color not in node[nex_2]:
                        n1,n2=0,0
                        if now > nex_2:
                            n1,n2 =nex_2,now
                        else:
                            n1,n2 =now,nex_2
                        edge[(n1,n2)] =color +1  #辺の色決定
                        node[now]   .append(color)
                        node[nex_2] .append(color)
                        passed[now] =True
                        #colored     =connection[nex_2] - passed
                        if passed[nex_2] ==False:
                            next_next.add(nex_2)  #つながっている頂点（次に探索する）
                        passed[nex_2] =nex_2
                        color   +=1
                        count   +=1
                        break
                    else:
                        color +=1
                        count +=1
        now_set     .clear()
        now_set     |=next_next
        next_next   .clear()
        
    #出力
    print(color_max)
    for i in A:
        print(edge[i])

Buggy submission (verdict: Runtime Error):
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #辺につながっている頂点に使った色
color_side =[0]*(N-1)
color =0
color_all =set(j for j in range(1,color_max +1) )
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    #while True:
    color =(color_all - color_vertex[v_a] -color_vertex[v_b]).pop() #全ての色-使った色[a]-使った色[b]

    color_side[i] =color          #辺の色を出力用に決める
    color_vertex[v_a].add(color)    #前の頂点に使った色として追加
    color_vertex[v_b].add(color)    #先の頂点に使った色として追加
              
#出力
print(color_max)
print(*color_side, sep="\n")

Buggy submission (verdict: Runtime Error):
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #辺につながっている頂点に使った色
color_side =[0]*(N-1)
color =0
color_all =set(j for j in range(1,color_max +1) )
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    #while True:
    color =(color_all - color_vertex[v_a] -color_vertex[v_b]).pop() #全ての色-使った色[a]-使った色[b]
    #if color not in color_vertex[A[i]] :  #使った色リストに入っているか？
    color_side[i] =color          #辺の色を出力用に決める（2行上の＋１）
    color_vertex[v_a].add(color)    #前の頂点に使った色として追加
    color_vertex[v_b].add(color)    #先の頂点に使った色として追加
          
        #    break
        #else:
         #   color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

Buggy submission (verdict: Runtime Error):
# 初期入力
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])

Buggy submission (verdict: Runtime Error):
# 初期入力
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])