Problem p02749 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

# input
N = int(input())
Edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)

# process
# 頂点を2グループに分類
group = [-1]*N
group[0] = False
def categorize2g(pi, i, g):
    for ci in Edges[i]:
        if ci == pi:
            continue
        group[ci] = not g
        categorize2g(i, ci, not g)

categorize2g(-1, 0, 0)

# 順列を求める
ans = [0]*N
mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]
gtnum = sum(group)
if gtnum <= N//3:
    dq = deque(mod1+mod2+mod0)
elif N-gtnum <= N//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)

if len(ans) == N:
    for i, g in enumerate(group):
        if g:
            ans[i] = dq.pop()
        else:
            ans[i] = dq.popleft()

# output
# print(group)
print(" ".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2*10**5)

# input
N = int(input())
Tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)
    Tree[b-1].append(a-1)

# process
def f(i):
    if tg[i] == 0 and mod3[1] <= N:
        ans[i] = mod3[1]
        mod3[1] += 3
    elif tg[i] == 1 and mod3[2] <= N:
        ans[i] = mod3[2]
        mod3[2] += 3
    elif mod3[0] <= N:
        ans[i] = mod3[0]
        mod3[0] += 3
    else:
        ans.clear()

    g = (tg[i]+1)%2
    for p in Tree[i]:
        if p == i or tg[p] != -1:
            continue
        
        tg[p] = g
        if not f(p):
            return False
    
    return True

tg = [-1]*N
tg[0] = 0
ans = [0]*N
mod3 = [3, 1, 2]

f(0)

# output
# print(tg)

if len(ans) == 0:
    if tg.count(0) < 2 or N - tg.count(0) < 2:
        ans = [0]*N
        for i in range(0, N):
            ans[i] = i+1
    else:
        ans = [-1]

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2*10**5)

# input
N = int(input())
Tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)
    Tree[b-1].append(a-1)

# process
# treeを2グループに分類
def to2g(tg, i):
    g = (tg[i]+1)%2
    for p in Tree[i]:
        if tg[p] == 1:
            continue
        tg[p] = g
        to2g(tg, p)

tg = [-1]*(N)
tg[0] = 0
to2g(tg, 0)

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

# output
print(" ".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2*10**5)

# input
N = int(input())
Tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    Tree[a-1].append(b-1)

# process
# treeを2グループに分類
def to2g(tg, i):
    g = (tg[i]+1)%2
    for p in Tree[i]:
        tg[p] = g
        to2g(tg, p)

tg = [-1]*(N)
tg[0] = 0
to2g(tg, 0)

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

# output
print(" ".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
#input
N = int(input())
Tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    Tree[a-1].append(b-1)

# process
# treeを2グループに分類
tg = [-1]*(N)
tg[0] = 0
for i, t in enumerate(Tree):
    g = (tg[i]+1)%2
    for p in t:
        tg[p] = g

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

# output
print(" ".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        return 0
    else:
        l = [n*3 for n in range(1, N//3+1)]

        for y in l:
            if not y in ans:
                return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N+1):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 0
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        if t == 0:
            continue
        elif t > 0:
            ans[b] = t
        else:
            ans = []
            break

for i in range(N):
    if ans[i] == -1:
        ans[i] = getNextNum(n, ans)

# output
# print(pair)
if len(ans) == 0:
    print(-1)
else:
    print(" ".join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        l = [n for n in range(1, N+1)]

    else:
        l = [n*3 for n in range(1, N//3+1)]

    for y in l:
        if not y in ans:
            return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 1
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = n
        n = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        ans[b] = t

for i in range(N):
    if ans[i] == -1:
        ans[i] = n
        n = getNextNum(n, ans)

# output
# print(pair)
print(" ".join(map(str, ans)))