Problem p02749 (python)

Fixed submission:
#####
 
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
sys.setrecursionlimit(10**6) 
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)

Buggy submission (verdict: Runtime Error):

#####

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)

Buggy submission (verdict: Runtime Error):

#####

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)

Buggy submission (verdict: Runtime Error):

#####

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)

Buggy submission (verdict: Runtime Error):
#####
 
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)

Buggy submission (verdict: Runtime Error):
#####

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)

Buggy submission (verdict: Runtime Error):
#####
 
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)

Buggy submission (verdict: Runtime Error):

#####

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)

Buggy submission (verdict: Runtime Error):

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

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)
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
# 	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, int8)
	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(remainingMod[0])*3+3
	values[values==1]=np.arange(remainingMod[1])*3+1
	values[values==2]=np.arange(remainingMod[2])*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
# 	
# 	print("testing")
# 	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:
# 				print(v0, val0, v1, val1, "ok")
# 			else:
# 				print(v0, val0, v1, val1, "NG")
		
	


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

Buggy submission (verdict: Runtime Error):

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

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)
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
# 	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, int8)
	if (depths==0).sum()<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=(depths==0).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif (depths==1).sum()<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=(depths==1).sum()
		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

	nextValue=[3,1,2]
	for i,v in enumerate(values):
		v3=v%3
		values[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,values)))

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

Buggy submission (verdict: Runtime Error):

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

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, d+1, 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)
	
	depths=np.empty(n, int32)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
	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, int8)
	if (depths==0).sum()<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=(depths==0).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif (depths==1).sum()<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=(depths==1).sum()
		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

	nextValue=[3,1,2]
	for i,v in enumerate(values):
		v3=v%3
		values[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,values)))

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

Buggy submission (verdict: Runtime Error):


#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

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(v, remaining, connected, nodes):
	nodes.append(v)
	for child in connected[v]:
		if child not in remaining: continue
		remaining.remove(child)
		dfs(child, remaining, connected, nodes)


def test(nodes, index, remainingMod, values, connected):
	node=nodes[index]
# 	print("node", node)
# 	print("values", values)
	
	possibleValues=np.array([remainingMod[v]>0 for v in range(3)], np.bool)
	ok=possibleValues.sum()>0
	if ok:
		for n1 in connected[node]:
			if n1 in values:
				if values[n1]==1:
					possibleValues[1]=False
				elif values[n1]==2:
					possibleValues[2]=False
				if possibleValues.sum()==0:
					ok=False
					break
	
# 	print("ok", ok)
	
	if not ok:
		return False
	
	for v in range(3):
		if not possibleValues[v]: continue
		values[node]=v
		remainingMod[v]-=1
		if index==len(nodes)-1:
			return True
		r=test(nodes, index+1, remainingMod, values, connected)
		if r:
			return True
		remainingMod[v]+=1
		
	values.pop(node)
	return False
		


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)
	
	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
	
# 	print(v3)
# 	for i in v3: print(i, v3[i])
# 	print()
	connected=v3
	
	nodes=sorted(range(1, n+1), key=lambda n:-len(connected[n]))
# 	print("nodes", nodes)
	
	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("remainingMod0", remainingMod)

	values={}
	r=test(nodes, 0, remainingMod, values, connected)
	if not r:
		print("-1")
		sys.exit(0)
		
# 	print(values)
	valueList=[values[n] for n in range(1, n+1)]
# 	print(valueList)
	nextValue=[3,1,2]
	for i,v in enumerate(valueList):
		v3=v%3
		valueList[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,valueList)))
		
	

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