Problem p02749 (python)

Fixed submission:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for j in [1, 2, 0]:
                if len(nums[j]) > 0:
                    ans[i] = nums[j].pop()
                    break

if cnts[0] <= n // 3:
    # print("A")
    solve(0)
elif cnts[1] <= n // 3:
    # print("B")
    solve(1)
else:
    # print("C")
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

print(" ".join(list(map(str, ans))))

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()


if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
elif cnts[0] > n // 3 and cnts[1] > n // 3:
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()
else:
    print(-1)
    exit()

print(" ".join(list(map(str, ans))))

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(idx, pre_3, pre_2, pre_1):
    if pre_1 == -1:
        if pre_1 % 3 == 2 and len(edges[1]) > 0:
            out = edges[1].pop()
        elif pre_1 % 3 == 1 and len(edges[2]) > 0:
            out = edges[2].pop()
        else:
            out = edges[0].pop()
    else:
        if pre_1 % 3 != 0:
            if pre_1 % 3 == 2 and len(edges[1]) > 0:
                out = nums[1].pop()
            elif pre_1 % 3 == 1 and len(edges[2]) > 0:
                out = nums[2].pop()
            else:
                if len(edges[0]) > 0:
                    out = edges[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(edges[1]) > 0:
                out = nums[1].pop()
            elif len(edges[2]) > 0:
                out = nums[2].pop()
            else:
                if len(edges[0]) > 0:
                    out = edges[0].pop()
                else:
                    print(-1)
                    exit()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

for i in range(1, n+1):
    if len(edges[i]) == 1:
        dfs(1, i, -1, -1, -1)
        break

print(" ".join(list(map(str, ans))))

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_3, pre_2, pre_1):
    pre_3_mod = pre_3 % 3
    if pre_3 == -1:
        if len(nums[step%3]) > 0:
            out = nums[step%3].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    out = nums[i].pop()
                    break
    else:
        if pre_3_mod != 0:
            if len(nums[3 - (pre_3_mod)]) > 0:
                out = nums[3 - (pre_3_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(ans)
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                out = nums[1].pop()
            else:
                out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

dfs(1, 1, -1, -1, -1)

print(" ".join(list(map(str, ans))))

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_2, pre_1):
    pre_2_mod = pre_2 % 3
    if pre_2 == -1:
        for i in [1, 2, 0]:
            if len(nums[i]) > 0:
                out = nums[i].pop()
                break
    else:
        if pre_2_mod != 0:
            if len(nums[3 - (pre_2_mod)]) > 0:
                out = nums[3 - (pre_2_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                out = nums[1].pop()
            else:
                out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_1, out)

dfs(1, 1, -1, -1)
print(" ".join(list(map(str, ans))))