Problem p02749 (python)

Fixed submission:
from collections import deque
n = int(input())
G = [[] for i in range(n)]

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

color = [-1] * n  # 木は二分グラフなので彩色

queue = deque([0])
color[0] = 0
red_blue = [1, 0]  # 色毎に塗った数を記録

while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == -1:
            color[to] = 1 - color[now]
            red_blue[color[to]] += 1
            queue.append(to)

ans = [-1] * n  # 異なる色が塗られたもの同士の数字がmod3で同じにならなければ十分
if 3*red_blue[0] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3*one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3*two+2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
elif 3*red_blue[1] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 1:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3 * one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3 * two + 2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
else:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            if 3*one+1 <= n:
                ans[i] = 3*one+1
                one += 1
            else:
                ans[i] = 3*three+3
                three += 1
        else:
            if 3*two+2 <= n:
                ans[i] = 3*two+2
                two += 1
            else:
                ans[i] = 3*three+3
                three += 1
                
print(*ans)

Buggy submission (verdict: Runtime Error):
from collections import deque,defaultdict

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

pa = defaultdict(int)
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = []
for i in range(n):
    if pa[pa[i]] != -1:
        Graph.append(G[pa[pa[i]]].copy())
    else:
        Graph.append([])
G = [[] for _ in range(n)]
for i in range(n):
    for j in Graph[i]:
        if j == pa[i]:continue
        G[i].append(j)
        G[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(G[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i <= n:
    ans[num[i-1][1]] = 3*i
    i += 1


use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in G[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)

Buggy submission (verdict: Runtime Error):
from collections import deque,defaultdict

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

pa = defaultdict(int)
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = []
for i in range(n):
    if pa[pa[i]] != -1:
        Graph.append(G[pa[pa[i]]].copy())
        Graph[-1].remove(pa[i])
    else:
        Graph.append([])
G = [[] for _ in range(n)]
for i in range(n):
    for j in Graph[i]:
        G[i].append(j)
        G[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(G[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i <= n:
    ans[num[i-1][1]] = 3*i
    i += 1


use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in G[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

pa = {}
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = []
for i in range(n):
    if pa[pa[i]] != -1:
        Graph.append(G[pa[pa[i]]].copy())
        Graph[-1].remove(pa[i])
    else:
        Graph.append([])
G = [[] for _ in range(n)]
for i in range(n):
    for j in Graph[i]:
        G[i].append(j)
        G[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(G[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i < n:
    ans[num[i-1][1]] = 3*i
    i += 1


use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in G[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)