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:
# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ

# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので

# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする

# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める


def main():
    from collections import deque
    from itertools import chain, tee
    import sys
    input = sys.stdin.readline

    # INPUT
    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0

    while dq:
        v = dq.popleft()
        p = parity[v]
        for u in graph[v]:
            if ~parity[u]: continue
            parity[u] = 1 ^ p
            dq.append(u)

    # SOLVE
    count_0 = parity.count(0)
    k = N // 3  # 3の倍数の個数

    g1 = range(1, N + 1, 3)
    g2 = range(2, N + 1, 3)
    g3 = range(3, N + 1, 3)
    g3f, g3r = tee(g3, 2)
    g12 = chain(g1, g2)
    g13 = chain(g1, g3f)
    g2r3 = chain(g2, reversed(g3r))
    if count_0 <= k:
        # parity=0を3の倍数で埋める
        # 残りを余った数で埋める
        for v in range(N):
            parity[v] = next(g3) if parity[v] == 0 else next(g12)

    elif N - count_0 <= k:
        # parity=1を3の倍数で埋める
        # 残りを余った数で埋める
        for v in range(N):
            parity[v] = next(g3) if parity[v] == 1 else next(g12)

    else:
        # parity=0を(mod3=1)で埋める
        # parity=1を(mod3=2)で埋める
        # 残りを3の倍数で埋める
        for v in range(N):
            if parity[v] == 0:
                parity[v] = next(g13)
            else:
                parity[v] = next(g2r3)

    print(*parity)


if __name__ == '__main__':
    main()

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()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
# 		counts[0]+=1
		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]:
# 		counts[1]+=1
		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:
# 		counts[2]+=1
		remaining=np.concatenate([1*np.ones(remainingMod[1], int32), np.zeros(sum0-remainingMod[1])])
		values[depths==0]=remaining
		remaining=np.concatenate([2*np.ones(remainingMod[2], int32), np.zeros(sum1-remainingMod[2])])
		values[depths==1]=remaining
	
	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:
# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ

# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので

# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする

# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める


def main():
    from collections import deque
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # INPUT
    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0

    while dq:
        v = dq.popleft()
        p = parity[v]
        for u in graph[v]:
            if ~parity[u]: continue
            parity[u] = 1 ^ p
            dq.append(u)

    # SOLVE
    count_0 = parity.count(0)
    k = N // 3  # 3の倍数の個数

    g1 = range(1, N + 1, 3)
    g2 = range(2, N + 1, 3)
    g3 = range(3, N + 1, 3)
    g12 = chain(g1, g2)
    g13 = chain(g1, g3)
    g2r3 = chain(g2, reversed(g3))
    if count_0 <= k:
        # parity=0を3の倍数で埋める
        # 残りを余った数で埋める
        for v in range(N):
            parity[v] = next(g3) if parity[v] == 0 else next(g12)

    elif N - count_0 <= k:
        # parity=1を3の倍数で埋める
        # 残りを余った数で埋める
        for v in range(N):
            parity[v] = next(g3) if parity[v] == 1 else next(g12)

    else:
        # parity=0を(mod3=1)で埋める
        # parity=1を(mod3=2)で埋める
        # 残りを3の倍数で埋める
        for v in range(N):
            if parity[v] == 0:
                parity[v] = next(g13)
            else:
                parity[v] = next(g2r3)

    print(*parity)


if __name__ == '__main__':
    main()

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()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=sum0
		
		index1=np.where(depths==1)[0]
		values[index1[:remainingMod[0]]]=0
		values[index1[remainingMod[0]:remainingMod[0]+remainingMod[1]]]=1
		values[index1[remainingMod[0]+remainingMod[1]:]]=2

	elif sum1<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=sum1
		
		index1=np.where(depths==0)[0]
		values[index1[:remainingMod[0]]]=0
		values[index1[remainingMod[0]:remainingMod[0]+remainingMod[1]]]=1
		values[index1[remainingMod[0]+remainingMod[1]:]]=2
		
	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:

#####

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()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=sum0
		
		index1=np.where(depths==1)[0]
		values[index1[:remainingMod[0]]]=0
		values[index1[remainingMod[0]:remainingMod[0]+remainingMod[1]]]=1
		values[index1[remainingMod[0]+remainingMod[1]:]]=2

	elif sum1<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=sum1
		
		index1=np.where(depths==0)[0]
		values[index1[:remainingMod[0]]]=0
		values[index1[remainingMod[0]:remainingMod[0]+remainingMod[1]]]=1
		values[index1[remainingMod[0]+remainingMod[1]:]]=2
		
	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
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())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N+1)]
ans = [0]*N
for a,b in ab:
  l[a].append(b)
  l[b].append(a)
  
r = [0]*(N+1)
i = 0
p = l[1]
q = deque()
flag = [False]*(N+1)
flag[1]=True
while (len(p)!=0)or(len(q)!=0):
  if i%2==0:
    while len(p)!=0:
      j = p.pop()
      if flag[j]:
        continue
      else:
        q.extend(l[j])
        flag[j]=True
        r[j]=1
    i+=1
  else:
    while len(q)!=0:
      j = q.pop()
      if flag[j]:
        continue
      else:
        p.extend(l[j])
        flag[j]=True
    i+=1
a = deque(range(1,N+1,3))
b = deque(range(2,N+1,3))
c = deque(range(3,N+1,3))
x = sum(r)
if x<=N//3:
  for i in range(1,N+1):
    if r[i]==1:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=b.pop()
elif (N-x)<=N//3:
  for i in range(1,N+1):
    if r[i]==0:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
else:
  for i in range(1,N+1):
    if r[i]==1:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=b.pop()
    else:
      if len(b)!=0:
        ans[i-1]=b.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=a.pop()
        
print(' '.join(map(str,ans)))

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()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
# 		counts[0]+=1
		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]:
# 		counts[1]+=1
		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:
# 		counts[2]+=1
		remaining=np.concatenate([1*np.ones(remainingMod[1], int32), np.zeros(sum0-remainingMod[1])])
		values[depths==0]=remaining
		remaining=np.concatenate([2*np.ones(remainingMod[2], int32), np.zeros(sum1-remainingMod[2])])
		values[depths==1]=remaining
	
	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=getInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(1000000000)

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print(" ".join(ans))

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()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
# 		counts[0]+=1
		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]:
# 		counts[1]+=1
		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:
# 		counts[2]+=1
		remaining=np.concatenate([1*np.ones(remainingMod[1], int32), np.zeros(sum0-remainingMod[1])])
		values[depths==0]=remaining
		remaining=np.concatenate([2*np.ones(remainingMod[2], int32), np.zeros(sum1-remainingMod[2])])
		values[depths==1]=remaining
	
	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:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N+1)]
ans = [0]*N
for a,b in ab:
  l[a].append(b)
  l[b].append(a)
  
r = [0]*(N+1)
i = 0
p = l[1]
q = deque()
flag = [False]*(N+1)
flag[1]=True
while (len(p)!=0)or(len(q)!=0):
  if i%2==0:
    while len(p)!=0:
      j = p.pop()
      if flag[j]:
        continue
      else:
        q.extend(l[j])
        flag[j]=True
        r[j]=1
    i+=1
  else:
    while len(q)!=0:
      j = q.pop()
      if flag[j]:
        continue
      else:
        p.extend(l[j])
        flag[j]=True
    i+=1
a = deque(range(1,N+1,3))
b = deque(range(2,N+1,3))
c = deque(range(3,N+1,3))
x = sum(r)
if x<=N//3:
  for i in range(1,N+1):
    if r[i]==1:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=b.pop()
elif (N-x)<=N//3:
  for i in range(1,N+1):
    if r[i]==0:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
else:
  for i in range(1,N+1):
    if r[i]==1:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=c.pop()
    else:
      if len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
        
print(' '.join(map(str,ans)))

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 = []
odd.append(1)

def add(x):
    for b in table[x-1]:
        if x == 1:
            odd.append(b)
            add(b)
        elif 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)]

def fill():
    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]

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:
from collections import Counter
import sys
sys.setrecursionlimit(1000000000)

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print("".join(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print("".join(ans))