Problem p02749 (python)

Fixed submission:
import sys
from collections import defaultdict, deque
readline = sys.stdin.readline

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if len(even) <= n // 3:
    odd, even = even, odd
if len(odd) <= n // 3:
    r = r2 + r1 + r0
else:
    r = r1 + r0 + r2
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] > num[1]:
   odd, even = even, odd
if num[0] > n / 3 and num[0] > n / 3:
    r = r2 + r0 + r1
else:
    r = r2 + r1 + r0
ans = [0] * n
for i in even:
    ans[i] = r.pop()
for i in odd:
    ans[i] = r.pop()
print(f'{odd=}{even=}{num=}')
print(*ans)

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    deg[a] += 1
    deg[b] += 1


q =  deque([deg.index(1)])
depth = [-1] * n
depth[q[0]] = 0
num = [0] * 2
d = 1
while q:
    x = q.popleft()
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
    d += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(2, n + 1, 3))
r2 = list(range(1, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
ans = [0] * n
if num[0] > n / 3 or num[1] > n / 3:
    for i in odd:
        if r1:
            ans[i] = r1.pop()
        else:
            ans[i] = r0.pop()
    for i in even:
        if r2:
            ans[i] = r2.pop()
        else:
            ans[i] = r0.pop()
elif num[0] > n / 3:
    for i in even:
        ans[i] = r0.pop()
    for i in odd:
        if r0:
            ans[i] = r0.pop()
        elif r1:
            ans[i] = r1.pop()
        elif r2:
            ans[i] = r2.pop()
elif num[0] > n / 3:
    for i in odd:
        ans[i] = r0.pop()
    for i in even:
        if r0:
            ans[i] = r0.pop()
        elif r1:
            ans[i] = r1.pop()
        elif r2:
            ans[i] = r2.pop()
print(*ans)

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    deg[a] += 1
    deg[b] += 1


def dist_3(i):
    q = deque([i])
    pair = []
    for a in G[i]:
        for b in G[a]:
            for c in G[b]:
                pair.append(c)
    return pair


ans = list(range(1, n+1))
idx = sorted(range(n), key=lambda x:deg[x])
for i in range(n//3):
    ans[idx[i]], ans[(i+1)*3] = ans[(i+1)*3], ans[idx[i]]
print(*ans)