Problem p02749 (python)

Fixed submission:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

from collections import deque

def calc_dist(G, start):
    que = deque()
    dep = [-1]*n
    que.append((-1,start,0))
    while que:
        p,v,d = que.pop()
        dep[v]=d
        for to in G[v]:
            if to != p:
                que.append((v,to,d+1))
    return dep

dep0 = calc_dist(G,0)
m = max(dep0)
left = dep0.index(m)
dep1 = calc_dist(G,left)
m = max(dep1)
right = dep1.index(m)
dep2 = calc_dist(G, right)

x = sum(i%2==0 for i in dep1)
y = n - x
ok = set()
for i in range(n):
    ma = max(dep1[i], dep2[i])
    if ma < 3:
        if dep1[i]%2 == 0:
            x -= 1
        else:
            y -= 1
        ok.add(i)

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)

ans = [0]*n
if x<y:
    one, two = two, one
for i in range(n):
    if i in ok:
        continue
    if dep1[i]%2 == 0:
        if one:
            ans[i] = one.pop()
        else:
            ans[i] = three.pop()
    else:
        if two:
            ans[i] = two.pop()
        else:
            ans[i] = three.pop()
res = one+two+three
for i in ok:
    ans[i] = res.pop()

print(*ans)