Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = n_in()
edges = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


# Euler Tour の構築
S = []
depth = [0]*N
visited = set()

def dfs(v, d):
    visited.add(v)
    depth[v] = d
    S.append(v)
    for w in edges[v]:
        if w in visited:
            continue
        dfs(w, d+1)
        S.append(v)


root = 0
dfs(root, 0)

res = [0 for _ in range(N)]

from collections import deque
q0 = deque(i for i in range(1,N+1) if i%3 == 0)
q1 = deque(i for i in range(1,N+1) if i%3 == 1)
q2 = deque(i for i in range(1,N+1) if i%3 == 2)

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth > N//3 and odd_depth > N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth <= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()


print_l(res)

Submission status: Runtime Error

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N-1)]
X = sorted(X, key = lambda x: (x[0], x[1]))

table = [[] for _ in range(N)]
for a, b in X:
    table[a-1].append(b)
odd = []
even = []
even.append(1)

def add(x):
    for b in table[x-1]:
        if x in even and b not in odd:
            odd.append(b)
            add(b)
        elif x in odd and b not in even:
            even.append(b)
    return 0

for i in range(1, N+1):
    add(i)
p = [i+1 for i in range(N)]
ans = [0 for i in range(N)]
if len(odd) <= N/3:
    for index, x in enumerate(odd):
        value = 3*(index+1)
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(even):
        ans[x-1] = p[index]

elif len(even) <= N/3:
    for index, x in enumerate(even):
        value = 3*(index+1)
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(odd):
        ans[x-1] = p[index]
else:
    if len(even) < len(odd):
        for index, x in enumerate(even):
            value = 3*index +1
            ans[x-1] = value
            p.remove(value)
        for index, x in enumerate(odd):
            ans[x-1] = p[index]
    else:
        for index, x in enumerate(odd):
            value = 3*index +1
            ans[x-1] = value
            p.remove(value)
        for index, x in enumerate(even):
            ans[x-1] = p[index]     
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

k0 = list(range(3, N + 1, 3))
k1 = list(range(1, N + 1, 3))  # 1番多い
k2 = list(range(2, N + 1, 3))

start = ab[0]
color = 1  # 1が黒
queue = deque([(start, color)])
answer = [0] * (N + 1)
answer[start] = k1.pop()
while queue:
    V, c = queue.popleft()
    c = -c
    for v in graph[V]:
        if answer[v] == 0:
            if c == 1:
                if k1:
                    answer[v] = k1.pop()
                else:
                    answer[v] = k0.pop()
            else:
                if k2:
                    answer[v] = k2.pop()
                else:
                    answer[v] = k0.pop()
            queue.append((v, c))

print(' '.join(map(str, answer[1:])))

Submission status: Runtime Error

Solution code:
#####
 
import numpy as np
from numpy import int32, int8
from collections import defaultdict
 
#####
 
def getIntList(inp):
	return [int(_) for _ in inp]
 
 
from sys import stdin
import sys
 
def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs
 
 
def dfs(node, depths, d, connected, parent):
	depths[node-1]=d
	for child in connected[node]:
		if child==parent: continue
		dfs(child, depths, not d, connected, node)
		
 
def main(inputs):
	n=int(inputs[0][0])
	
	edge=defaultdict(list)
	for i in range(n-1):
		a,b=getIntList(inputs[1+i])
		edge[a].append(b)
		edge[b].append(a)
	
# 	for v0 in sorted(edge): print(v0, sorted(edge[v0]))
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	for i in range(n):print(i+1,depths[i])
# 	depths%=2
	
	m=n%3
	if m==0: remainingMod=[n//3,n//3,n//3]
	elif m==1: remainingMod=[n//3,n//3+1,n//3]
	elif m==2: remainingMod=[n//3,n//3+1,n//3+1]
# 	print(remainingMod)
	
	values=np.empty(n, int32)
	sum0=(depths==0).sum()
	sum1=(depths==1).sum()
	if sum0<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=sum0
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==1]=remaining
	
	elif sum1<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=sum1
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==0]=remaining
		
	else:
		index0=np.where(depths==0)[0]
		index1=np.where(depths==1)[0]
		
		values[index0[:remainingMod[1]]]=1
		values[index1[:remainingMod[2]]]=2
		
		values[index0[remainingMod[1]:]]=0
		values[index1[remainingMod[2]:]]=0
	
	values[values==0]=np.arange((values==0).sum())*3+3
	values[values==1]=np.arange((values==1).sum())*3+1
	values[values==2]=np.arange((values==2).sum())*3+2
	print(" ".join(map(str,values)))
	
# 	v3=defaultdict(list)
# 	for i in range(1,n+1):
# 		visited=set([i])
# 		prev=[i]
# 		for count in range(3):
# 			next=[]
# 			for node in prev:
# 				for child in edge[node]:
# 					if child in visited: continue
# 					next.append(child)
# 			visited.update(next)
# 			prev=next
# # 			print(i, next)
# 		v3[i]=next
# 	
# # 	for v0 in sorted(v3):
# # 		print(v0, sorted(v3[v0]))
# 	
# # 	print("testing")
# 	ok=True
# 	for v0 in v3:
# 		for v1 in v3[v0]:
# 			val0=values[v0-1]
# 			val1=values[v1-1]
# 			if (val0+val1)%3==0 or (val0*val1)%3==0:
# 				pass
# # 				print(v0, val0%3, v1, val1%3, "ok")
# 			else:
# # 				print(v0, val0%3, v1, val1%3, "NG")
# 				ok=False
# 	assert ok
 
 
if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import Counter

N = int(input())
T = [set() for x in range(N)]
search = [0] * N
isOdd = [0] * N

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

Q = deque()

search[0] = 1
Q.append(0)
dlen = 1
while dlen != 0:
    q = Q.pop()
    dlen -= 1
    for aa in T[q]:
        if search[aa]:
            continue
        search[aa] = 1
        Q.append(aa)
        dlen += 1
        isOdd[aa] = isOdd[q] ^ 1

C = Counter(isOdd)

a = []
if C[0] <= N // 3:
    a = lambda x:[1,0,-1][x%3]
elif C[1] <= N // 3:
    a = lambda x:[-1,0,1][x%3]
else:
    a = 1 // 0
    a = lambda x:[0,-1,1][x%3]

d = deque(sorted(range(1,N+1),key=a))
print(*[d.pop() if isOdd[x] else d.popleft() for x in range(N)],sep=" ")

Submission status: Runtime Error

Solution code:
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


al = [0, 0]
for d in dist:
    al[d%2] += 1
if sum(al) // al[0] > 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] > 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

al = [0, 0, 0]
for d in dist:
    al[d%3] += 1
if sum(al) // al[0] > 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] > 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)

Submission status: Runtime Error

Solution code:

#####

import numpy as np
from numpy import int32, int8
from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def dfs(node, depths, d, connected, parent):
	depths[node-1]=d
	for child in connected[node]:
		if child==parent: continue
		dfs(child, depths, not d, connected, node)
		

def main(inputs):
	n=int(inputs[0][0])
	
	edge=defaultdict(list)
	for i in range(n-1):
		a,b=getIntList(inputs[1+i])
		edge[a].append(b)
		edge[b].append(a)
	
# 	for v0 in sorted(edge): print(v0, sorted(edge[v0]))
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	for i in range(n):print(i+1,depths[i])
# 	depths%=2
	
	m=n%3
	if m==0: remainingMod=[n//3,n//3,n//3]
	elif m==1: remainingMod=[n//3,n//3+1,n//3]
	elif m==2: remainingMod=[n//3,n//3+1,n//3+1]
# 	print(remainingMod)
	
	values=np.empty(n, int32)
	sum0=(depths==0).sum()
	sum1=(depths==1).sum()
	if sum0<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=sum0
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif sum1<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=sum1
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==0]=remaining
		
	else:
		index0=np.where(depths==0)[0]
		index1=np.where(depths==1)[0]
		
		values[index0[:remainingMod[1]]]=1
		values[index1[:remainingMod[2]]]=2
		
		values[index0[remainingMod[1]:]]=0
		values[index1[remainingMod[2]:]]=0
	
	values[values==0]=np.arange((values==0).sum())*3+3
	values[values==1]=np.arange((values==1).sum())*3+1
	values[values==2]=np.arange((values==2).sum())*3+2
	print(" ".join(map(str,values)))
	
# 	v3=defaultdict(list)
# 	for i in range(1,n+1):
# 		visited=set([i])
# 		prev=[i]
# 		for count in range(3):
# 			next=[]
# 			for node in prev:
# 				for child in edge[node]:
# 					if child in visited: continue
# 					next.append(child)
# 			visited.update(next)
# 			prev=next
# # 			print(i, next)
# 		v3[i]=next
# 	
# # 	for v0 in sorted(v3):
# # 		print(v0, sorted(v3[v0]))
# 	
# # 	print("testing")
# 	ok=True
# 	for v0 in v3:
# 		for v1 in v3[v0]:
# 			val0=values[v0-1]
# 			val1=values[v1-1]
# 			if (val0+val1)%3==0 or (val0*val1)%3==0:
# 				pass
# # 				print(v0, val0%3, v1, val1%3, "ok")
# 			else:
# # 				print(v0, val0%3, v1, val1%3, "NG")
# 				ok=False
# 	assert ok


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N / 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N / 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for k in range(1, N + 1):
    modfit(k)

print()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, 0, 0)
zCnt = len(nums[0])

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(even) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    rest = nums[0]
    for i in even:
        ans[i] = rest.pop()
    for i in odd:
        ans[i] = rest.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, 0, 0)
zCnt = len(nums[0])

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(even) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    rest = nums[0]
    for i in even:
        ans[i] = rest.pop()
    for i in odd:
        ans[i] = rest.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for k in range(1, N + 1):
    modfit(k)

print()

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, 0, 0)
zCnt = N // 3

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(even) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    for i in even:
        ans[i] = nums[0].pop()
    for i in odd:
        ans[i] = nums[0].pop()

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    l_hen = [tuple(map(int, input().split())) for _ in range(n-1)]

    def dfs(node_num,dis,pre,org):
        if dis == 2:
            for hena, henb in l_hen:
                if hena == node_num and henb != pre:
                    combi.append((min(org, henb), max(org, henb)))
                elif henb == node_num and hena != pre:
                    combi.append((min(org, hena), max(org, hena)))
        else:
            for hena, henb in l_hen:
                if hena == node_num and henb != pre:
                    dfs(henb, dis + 1, node_num,org)
                elif henb == node_num and hena != pre:
                    dfs(hena, dis + 1, node_num,org)


    combi = []
    for node in range(1, n+1):
        for hena, henb in l_hen:
            if hena == node:
                dfs(henb, 1, node,node)
            elif henb == node:
                dfs(hena, 1, node,node)
    combi = set(combi)
    combi = list(combi)

    list1 = [0 for _ in range(n+1)]
    list2 = [0 for _ in range(n+1)]
    # まず「組」それぞれの片方を３の倍数の位置におく。置いたら組の片割れが未配置ならひとつ前の位置に置く。
    for i in range(1, (n // 3)+1):
        com_a, com_b = combi[i]
        if not list2[com_a]:
            list1[i * 3] = com_a
            list2[com_a] = i * 3
            if not list2[com_b]:
                list1[i * 3 - 1] = com_b
                list2[com_b] = i * 3 -1
        elif not list2[com_b]:
            list1[i * 3] = com_b
            list2[com_b] = i * 3
            if not list2[com_a]:
                list1[i * 3 -1] = com_a
                list2[com_a] = i * 3 - 1

    # 「組」の未配置のものを配置する
    for com_a, com_b in combi:
        # 組のどちらかが配置済みだったら

        if (list2[com_a] and not list2[com_b]) or (not list2[com_a] and list2[com_b]):
            if list2[com_a] and not list2[com_b]:
                for k in range(1, n+1):
                    if not list2[com_b] and k != list2[com_a] and not list1[k] and (k * list2[com_a]) % 3 == 0:
                        list1[k] = com_b
                        list2[com_b] = k
                    elif not list2[com_a] and k != list2[com_a] and not list1[k] and (k + list2[com_a]) % 3 == 0:
                        list1[k] = com_b
                        list2[com_b] = k
            elif not list2[com_a] and list2[com_b]:
                for k in range(1, n+1):
                    if  k != list2[com_b] and not list1[k] and (k * list2[com_b]) % 3 == 0:
                        list1[k] = com_a
                        list2[com_a] = k
                    elif k != list2[com_b] and not list1[k] and (k + list2[com_b]) % 3 == 0:
                        list1[k] = com_a
                        list2[com_a] = k
        # 組の両方とも未配置だったら
        elif not list2[com_a] and not list2[com_b]:

            for j in range(1,n+1):
                for l in range(1,n+1):
                    if not list1[j] and not list1[l] and (j + l) %3 == 0:
                        list1[j] = com_a
                        list1[l] = com_b
                        list2[com_a] = j
                        list2[com_b] = l
                    elif not list1[j] and not list1[l] and (j * l) %3 == 0:
                        list1[j] = com_a
                        list1[l] = com_b
                        list2[com_a] = j
                        list2[com_b] = l
                    else:
                        print(-1)
                        exit()


    for m in range(1, n+1):
        if not list2[m]:
            for o in range(1, n+1):
                if not list1[o]:
                    list1[o] = m
                    list2[m] = o
                    break
    
    del(list2[0])
    if all(list2):
        for i in range(1, n+1):
            print(list1[i], end=' ')
    else:
        print(-1)

if __name__ == '__main__':
    main()