Social Infrastructure Information Systems Division  Hitachi Programming Contest 2020 - ThREE

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.

Example

Input

5
1 2
1 3
3 4
3 5


Output

1 2 5 4 3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even = []
nums = [[], [], []]
for i in range(1, n + 1):
	nums[i % 3].append(i)

def dfs(x, last=-1, d=0):
	if d % 2 == 0:
		even.append(x)
	else:
		odd.append(x)
	for nxt in edge[x]:
		if nxt == last:
			continue
		dfs(nxt, x, d + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
dfs(0)
zerocnt = len(nums[0])
if len(even) <= zerocnt:
	for even_node in even:
		ans[even_node] = nums[0].pop()
	rest = nums[0] + nums[1] + nums[2]
	for odd_node in odd:
		ans[odd_node] = rest.pop()
elif len(odd) <= zerocnt:
	for odd_node in odd:
		ans[odd_node] = nums[0].pop()
	rest = nums[0] + nums[1] + nums[2]
	for even_node in even:
		ans[even_node] = rest.pop()
else:
	for num in nums[1]:
		ans[even.pop()] = num
	for num in nums[2]:
		ans[odd.pop()] = num
	rest = nums[0]
	for even_node in even:
		ans[even_node] = rest.pop()
	for odd_node in odd:
		ans[odd_node] = rest.pop()
print(*ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def dfs(u=0, pu=-1, color=0):
		cc[u] = color
		cntc[color] += 1
		for cu in to1[u]:
			if pu == cu:
				continue
			dfs(cu, u, 1 - color)
	n = II()
	to1 = [set() for _ in range(n)]
	cc = [0] * n
	cntc = [0] * 2
	for _ in range(n - 1):
		(a, b) = MI1()
		to1[a].add(b)
		to1[b].add(a)
	dfs()
	m1 = (n - 1) // 3 + 1
	m2 = (n - 2) // 3 + 1
	m3 = n // 3
	if cntc[0] < cntc[1]:
		mnc = 0
	else:
		mnc = 1
	p1 = list(range(1, n + 1, 3))
	p2 = list(range(2, n + 1, 3))
	p3 = list(range(3, n + 1, 3))
	ans = [-1] * n
	if cntc[mnc] <= m3:
		for u in range(n):
			if cc[u] == mnc:
				ans[u] = p3.pop()
			elif p1:
				ans[u] = p1.pop()
			elif p2:
				ans[u] = p2.pop()
			else:
				ans[u] = p3.pop()
	elif cntc[1 - mnc] > m1 + m3:
		print(-1)
		exit()
	else:
		for u in range(n):
			if cc[u] == mnc:
				if p2:
					ans[u] = p2.pop()
				else:
					ans[u] = p3.pop()
			elif p1:
				ans[u] = p1.pop()
			else:
				ans[u] = p3.pop()
	print(*ans)
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	n = I()
	v = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = LI()
		a -= 1
		b -= 1
		v[a].append(b)
		v[b].append(a)
	if n < 4:
		print(*range(1, n + 1), sep=' ')
		return
	d = [-1] * n
	d[0] = 0
	q = deque([0])
	while q:
		x = q.popleft()
		nd = d[x] ^ 1
		for y in v[x]:
			if d[y] < 0:
				d[y] = nd
				q.append(y)
	n1 = sum(d)
	n0 = len(d) - n1
	if n1 > n0:
		for i in range(n):
			d[i] ^= 1
		(n0, n1) = (n1, n0)
	p = [(n + 2) // 3, (n + 1) // 3, n // 3]
	k = [1, 2, 3]
	ans = [0] * n
	if n1 >= p[1]:
		for i in range(n):
			di = d[i]
			if not p[di]:
				di = 2
			ans[i] = k[di]
			k[di] += 3
			p[di] -= 1
	else:
		for i in range(n):
			di = d[i]
			if di == 1:
				di = 2
			while not p[di]:
				di += 1
			ans[i] = k[di]
			k[di] += 3
			p[di] -= 1
	print(*ans)
	return
solve()


n = int(input())
lst = [[] for i in range(n + 1)]
for i in range(n - 1):
	(ai, bi) = map(int, input().split())
	lst[ai].append(bi)
	lst[bi].append(ai)
tf = [0 for i in range(n + 1)]
tf[1] = 1
iro = 1
queue = lst[1]
while queue != []:
	iro = -iro
	new_queue = []
	for i in queue:
		if tf[i] == 0:
			tf[i] = iro
			for j in lst[i]:
				if tf[j] == 0:
					new_queue.append(j)
	queue = new_queue
n_minus = tf.count(-1)
n_plus = tf.count(1)
ans = [0 for i in range(n)]
if n_minus <= n // 3:
	bai = 1
	for i in range(1, n + 1):
		if tf[i] == -1:
			ans[i - 1] = 3 * bai
			bai += 1
	kouho = 1
	for i in range(1, n + 1):
		if tf[i] == 1:
			if bai <= n // 3:
				ans[i - 1] = 3 * bai
				bai += 1
			else:
				ans[i - 1] = kouho
				kouho += 1
				if kouho % 3 == 0:
					kouho += 1
elif n_plus <= n // 3:
	bai = 1
	for i in range(1, n + 1):
		if tf[i] == 1:
			ans[i - 1] = 3 * bai
			bai += 1
	kouho = 1
	for i in range(1, n + 1):
		if tf[i] == -1:
			if bai <= n // 3:
				ans[i - 1] = 3 * bai
				bai += 1
			else:
				ans[i - 1] = kouho
				kouho += 1
				if kouho % 3 == 0:
					kouho += 1
else:
	bai = 1
	kouho1 = 1
	kouho2 = 2
	for i in range(1, n + 1):
		if tf[i] == 1:
			if kouho1 <= n:
				ans[i - 1] = kouho1
				kouho1 += 3
			else:
				ans[i - 1] = 3 * bai
				bai += 1
		elif kouho2 <= n:
			ans[i - 1] = kouho2
			kouho2 += 3
		else:
			ans[i - 1] = 3 * bai
			bai += 1
print(' '.join(map(str, ans)))


from collections import deque
N = int(input())
G = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
	if i % 3 == 1:
		one.append(i)
	elif i % 3 == 2:
		two.append(i)
	else:
		zero.append(i)
q = deque([1])
dist[1] = 0
while q.__len__() != 0:
	s = q.popleft()
	for i in G[s]:
		if dist[i] == -1:
			q.append(i)
			dist[i] = (dist[s] + 1) % 2
red = 0
blue = 0
for i in range(1, N + 1):
	if dist[i] == 0:
		red += 1
	else:
		blue += 1
ans = []
if red > N / 3 and blue > N / 3:
	for i in range(1, N + 1):
		if dist[i] == 0 and one.__len__() != 0:
			ans.append(one.pop())
		elif dist[i] == 1 and two.__len__() != 0:
			ans.append(two.pop())
		else:
			ans.append(zero.pop())
elif red <= N / 3:
	for i in range(1, N + 1):
		if dist[i] == 0:
			ans.append(zero.pop())
		elif one.__len__() != 0:
			ans.append(one.pop())
		elif two.__len__() != 0:
			ans.append(two.pop())
		else:
			ans.append(zero.pop())
else:
	for i in range(1, N + 1):
		if dist[i] == 1:
			ans.append(zero.pop())
		elif one.__len__() != 0:
			ans.append(one.pop())
		elif two.__len__() != 0:
			ans.append(two.pop())
		else:
			ans.append(zero.pop())
print(*ans)


import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
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)
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()
print(' '.join(map(str, ans)))


from collections import deque

def resolve():
	N = int(input())
	tree = [[] for i in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		tree[a - 1].append(b - 1)
		tree[b - 1].append(a - 1)
	d = deque([[0, -1]])
	dist = [0] * N
	while d:
		(node, par) = d.pop()
		children = tree[node]
		for child in children:
			if child == par:
				continue
			dist[child] = (dist[node] + 1) % 2
			d.appendleft([child, node])
	count0 = dist.count(0)
	count1 = N - count0
	s = [set(), set(), set()]
	for i in range(1, N + 1):
		s[i % 3].add(i)
	if count0 > N // 3:
		if count1 > N // 3:
			for i in range(N):
				if dist[i]:
					if s[2]:
						dist[i] = s[2].pop()
					else:
						dist[i] = s[0].pop()
				elif s[1]:
					dist[i] = s[1].pop()
				else:
					dist[i] = s[0].pop()
		else:
			for i in range(N):
				if dist[i]:
					dist[i] = s[0].pop()
				elif s[2]:
					dist[i] = s[2].pop()
				elif s[1]:
					dist[i] = s[1].pop()
				else:
					dist[i] = s[0].pop()
	else:
		for i in range(N):
			if dist[i]:
				if s[2]:
					dist[i] = s[2].pop()
				elif s[1]:
					dist[i] = s[1].pop()
				else:
					dist[i] = s[0].pop()
			else:
				dist[i] = s[0].pop()
	print(*dist)
resolve()


g = {}
n = int(input())
m = [-1] * n
import sys
sys.setrecursionlimit(1000000000)

def dfs(graph, node, height):
	global m
	global zeros
	global ones
	m[node - 1] = height
	if height == 0:
		zeros += 1
	if height == 1:
		ones += 1
	for n in graph[node]:
		if m[n - 1] == -1:
			dfs(graph, n, 1 - height)
zeros = 0
ones = 0
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if not a in g:
		g[a] = [b]
	else:
		g[a].append(b)
	if not b in g:
		g[b] = [a]
	else:
		g[b].append(a)
dfs(g, 1, 0)
ans = [0] * n
used = [0] * n
r = n // 3
if 3 * (r + 1) <= n:
	r += 1
if zeros <= r:
	current = 3
	for i in range(n):
		if m[i] == 0:
			ans[i] = current
			used[current - 1] = 1
			current += 3
	counter = 0
	for i in range(n):
		if m[i] == 1:
			while True:
				if used[counter] == 0:
					ans[i] = counter + 1
					counter += 1
					break
				counter += 1
elif ones <= r:
	current = 3
	for i in range(n):
		if m[i] == 1:
			ans[i] = current
			used[current - 1] = 1
			current += 3
	counter = 0
	for i in range(n):
		if m[i] == 0:
			while True:
				if used[counter] == 0:
					ans[i] = counter + 1
					counter += 1
					break
				counter += 1
elif zeros < ones:
	current = 1
	for i in range(n):
		if m[i] == 0:
			ans[i] = current
			used[current - 1] = 1
			current += 3
			if current > n:
				current = 3
	counter = 0
	for i in range(n):
		if m[i] == 1:
			while True:
				if used[counter] == 0:
					ans[i] = counter + 1
					counter += 1
					break
				counter += 1
else:
	current = 1
	for i in range(n):
		if m[i] == 1:
			ans[i] = current
			used[current - 1] = 1
			current += 3
			if current > n:
				current = 3
		counter = 0
	for i in range(n):
		if m[i] == 0:
			while True:
				if used[counter] == 0:
					ans[i] = counter + 1
					counter += 1
					break
				counter += 1
for i in ans:
	print(i)


import queue
N = int(input())
e = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	e[a].append(b)
	e[b].append(a)
even_v = []
odd_v = []
is_reached = [False] * (N + 1)
q = queue.Queue()
q.put([1, 0])
while not q.empty():
	(v, d) = q.get()
	if is_reached[v]:
		continue
	is_reached[v] = True
	if d % 2 == 0:
		even_v.append(v)
	else:
		odd_v.append(v)
	for tv in e[v]:
		q.put([tv, d + 1])
r1 = list(range(1, N + 1, 3))
r2 = list(range(2, N + 1, 3))
r3 = list(range(3, N + 1, 3))
ans = [0] * N
if len(even_v) <= len(r3):
	for v in even_v:
		ans[v - 1] = r3.pop()
elif len(odd_v) <= len(r3):
	for v in odd_v:
		ans[v - 1] = r3.pop()
else:
	for v in even_v:
		if not r1:
			break
		ans[v - 1] = r1.pop()
	for v in odd_v:
		if not r2:
			break
		ans[v - 1] = r2.pop()
rv = []
rv.extend(r1)
rv.extend(r2)
rv.extend(r3)
for (i, p) in enumerate(ans):
	if p == 0:
		ans[i] = rv.pop()
print(' '.join(list(map(str, ans))))


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def dfs(s, p):
	for v in edges[s]:
		if v == p:
			continue
		dist[v] = dist[s] + 1
		dfs(v, s)
	return
n = I()
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = LI()
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
dist = [0] * n
dfs(0, -1)
(R, B) = (0, 0)
(r, b) = ([], [])
for i in range(n):
	if dist[i] % 2:
		R += 1
		r.append(i)
	else:
		B += 1
		b.append(i)
ans = [None] * n
f = defaultdict(lambda : 0)
if R <= n // 3:
	tmp = 3
	for i in r:
		ans[i] = tmp
		f[tmp] = 1
		tmp += 3
	for i in range(1, n + 1):
		if f[i]:
			continue
		if b:
			v = b.pop()
			ans[v] = i
			f[i] = 1
elif B <= n // 3:
	tmp = 3
	for i in b:
		ans[i] = tmp
		f[tmp] = 1
		tmp += 3
	for i in range(1, n + 1):
		if f[i]:
			continue
		if r:
			v = r.pop()
			ans[v] = i
			f[i] = 1
else:
	for i in range(1, n + 1):
		if i % 3 == 1:
			if r:
				v = r.pop()
				ans[v] = i
				f[i] = 1
				continue
		elif i % 3 == 2:
			if b:
				v = b.pop()
				ans[v] = i
				f[i] = 1
				continue
	for i in range(1, n + 1):
		if i % 3 == 0:
			if r:
				ans[r.pop()] = i
			elif b:
				ans[b.pop()] = i
print(*ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ns[u].add(v)
	ns[v].add(u)

def is_bip(ns):
	start = 0
	q = [start]
	cs = [None] * n
	cs[start] = 1
	while q:
		u = q.pop()
		c = cs[u]
		cc = int(not c)
		for v in ns[u]:
			if cs[v] is None:
				cs[v] = cc
				q.append(v)
			elif cs[v] == c:
				return (False, None)
	return (True, cs)
(_, cs) = is_bip(ns)
(v1, v0) = (0, 0)
for num in cs:
	if num == 0:
		v0 += 1
	else:
		v1 += 1
num0 = [i for i in range(1, n + 1) if i % 3 == 0]
num1 = [i for i in range(1, n + 1) if i % 3 == 1]
num2 = [i for i in range(1, n + 1) if i % 3 == 2]
if v0 <= len(num0) or v1 <= len(num0):
	if v0 <= len(num0):
		val = 0
	else:
		val = 1
	for i in range(n):
		if cs[i] == val:
			cs[i] = num0.pop()
		elif num1:
			cs[i] = num1.pop()
		elif num2:
			cs[i] = num2.pop()
		else:
			cs[i] = num0.pop()
else:
	if v0 <= v1:
		val = 0
	else:
		val = 1
	for i in range(n):
		if cs[i] == val:
			if num1:
				cs[i] = num1.pop()
			else:
				cs[i] = num0.pop()
		elif num2:
			cs[i] = num2.pop()
		else:
			cs[i] = num0.pop()
write(' '.join(map(str, cs)))


from collections import deque
n = int(input())
E = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a = a - 1
	b = b - 1
	E[a].append(b)
	E[b].append(a)
D = deque([0])
V = [0] * n
V[0] = 1
A = [0] * n
k = 1
while len(D) > 0:
	x = D[0]
	D.popleft()
	for i in range(len(E[x])):
		if V[E[x][i]] == 0:
			V[E[x][i]] = 1
			D.append(E[x][i])
			A[E[x][i]] = A[x] ^ 1
f = 0
if n - sum(A) > sum(A):
	f = 1
g = max(n - sum(A), sum(A))
a = (n + 2) // 3
b = n // 3
if g > a + b:
	Ans = [0] * n
	s = 1
	t = 2
	u = 3
	if f == 0:
		for i in range(n):
			if A[i] == 0:
				Ans[i] = u
				u = u + 3
			elif s <= n:
				Ans[i] = s
				s = s + 3
			elif t <= n:
				Ans[i] = t
				t = t + 3
			else:
				Ans[i] = u
				u = u + 3
	else:
		for i in range(n):
			if A[i] == 1:
				Ans[i] = u
				u = u + 3
			elif s <= n:
				Ans[i] = s
				s = s + 3
			elif t <= n:
				Ans[i] = t
				t = t + 3
			else:
				Ans[i] = u
				u = u + 3
else:
	Ans = [0] * n
	s = 1
	t = 2
	u = 3
	if f == 1:
		for i in range(n):
			if A[i] == 0 and s <= n:
				Ans[i] = s
				s = s + 3
			elif A[i] == 0 and s > n:
				Ans[i] = u
				u = u + 3
			elif A[i] == 1 and t <= n:
				Ans[i] = t
				t = t + 3
			else:
				Ans[i] = u
				u = u + 3
	else:
		for i in range(n):
			if A[i] == 1 and s <= n:
				Ans[i] = s
				s = s + 3
			elif A[i] == 1 and s > n:
				Ans[i] = u
				u = u + 3
			elif A[i] == 0 and t <= n:
				Ans[i] = t
				t = t + 3
			else:
				Ans[i] = u
				u = u + 3
print(*Ans)


import sys
from collections import deque

def NC_Dij(lis, start):
	ret = [float('inf')] * len(lis)
	ret[start] = 0
	q = deque([start])
	plis = [i for i in range(len(lis))]
	while len(q) > 0:
		now = q.popleft()
		for nex in lis[now]:
			if ret[nex] > ret[now] + 1:
				ret[nex] = ret[now] + 1
				plis[nex] = now
				q.append(nex)
	return (ret, plis)
N = int(input())
lis = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	lis[a].append(b)
	lis[b].append(a)
(dis, plis) = NC_Dij(lis, 0)
use = [1, 2, 3]
flag = True
ans = []
for i in range(N):
	nex = use[dis[i] % 2]
	use[dis[i] % 2] += 3
	if nex > N:
		nex = use[2]
		use[2] += 3
	if nex > N:
		flag = False
		break
	ans.append(nex)
if flag:
	print(' '.join(map(str, ans)))
	sys.exit()
use = [2, 1, 3]
flag = True
ans = []
for i in range(N):
	nex = use[dis[i] % 2]
	use[dis[i] % 2] += 3
	if nex > N:
		nex = use[2]
		use[2] += 3
	if nex > N:
		flag = False
		break
	ans.append(nex)
if flag:
	print(' '.join(map(str, ans)))
	sys.exit()
use = [3, 1, 2]
flag = True
ans = []
for i in range(N):
	nex = use[dis[i] % 2]
	use[dis[i] % 2] += 3
	if nex > N and nex % 3 == 1:
		nex = use[2]
		use[2] += 3
	if nex > N and nex % 3 == 2:
		nex = use[0]
		use[0] += 3
	if nex > N:
		flag = False
		break
	ans.append(nex)
if flag:
	print(' '.join(map(str, ans)))
	sys.exit()
use = [1, 3, 2]
flag = True
ans = []
for i in range(N):
	nex = use[dis[i] % 2]
	use[dis[i] % 2] += 3
	if nex > N and nex % 3 == 1:
		nex = use[2]
		use[2] += 3
	if nex > N and nex % 3 == 2:
		nex = use[1]
		use[1] += 3
	if nex > N:
		flag = False
		break
	ans.append(nex)
if flag:
	print(' '.join(map(str, ans)))
	sys.exit()
print(-1)


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)
vertice = [-1 for _ in range(n)]
stack = [(0, 0)]
while stack:
	(parent, vertex) = stack.pop()
	vertice[vertex] = vertice[parent] * -1
	for next in edges[vertex]:
		if next != parent:
			stack.append((vertex, next))
ans = []
if vertice.count(1) <= n // 3:
	not3 = [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:
		if v == 1:
			if num3:
				ans.append(str(num3.pop()))
			else:
				ans.append(str(not3.pop()))
		elif not3:
			ans.append(str(not3.pop()))
		else:
			ans.append(str(num3.pop()))
elif vertice.count(-1) <= n // 3:
	not3 = [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:
		if v == -1:
			if num3:
				ans.append(str(num3.pop()))
			else:
				ans.append(str(not3.pop()))
		elif not3:
			ans.append(str(not3.pop()))
		else:
			ans.append(str(num3.pop()))
else:
	num1 = [i for i in range(1, n + 1) if i % 3 == 1]
	num2 = [i for i in range(1, n + 1) if i % 3 == 2]
	num3 = [i for i in range(1, n + 1) if i % 3 == 0]
	for v in vertice:
		if v == 1:
			if num1:
				ans.append(str(num1.pop()))
			else:
				ans.append(str(num3.pop()))
		elif num2:
			ans.append(str(num2.pop()))
		else:
			ans.append(str(num3.pop()))
print(' '.join(ans))


import sys
from collections import deque, Counter
n = int(input())
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	es[a].append(b)
	es[b].append(a)
depth = [-1 for _ in range(n + 1)]
dq = deque([1])
depth[1] = 0
while dq:
	v = dq.pop()
	for e in es[v]:
		if depth[e] != -1:
			continue
		depth[e] = depth[v] + 1
		dq.append(e)
ans = [-1 for _ in range(n + 1)]
cnt_dict = Counter([x % 2 for x in depth[1:]])
nums = [[i for i in range(1, n + 1) if i % 3 == 1], [i for i in range(1, n + 1) if i % 3 == 2], [i for i in range(1, n + 1) if i % 3 == 0]]
if cnt_dict[0] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			ans[i] = nums[2].pop()
		elif nums[0]:
			ans[i] = nums[0].pop()
		elif nums[1]:
			ans[i] = nums[1].pop()
		else:
			ans[i] = nums[2].pop()
elif cnt_dict[1] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 1:
			ans[i] = nums[2].pop()
		elif nums[0]:
			ans[i] = nums[0].pop()
		elif nums[1]:
			ans[i] = nums[1].pop()
		else:
			ans[i] = nums[2].pop()
else:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			if nums[0]:
				ans[i] = nums[0].pop()
			else:
				ans[i] = nums[2].pop()
		elif nums[1]:
			ans[i] = nums[1].pop()
		else:
			ans[i] = nums[2].pop()
print(*ans[1:])


from collections import deque

def bfs():
	q = deque()
	q.append(1)
	dist = [-1] * (n + 1)
	dist[1] = 0
	while q:
		p = q.popleft()
		for i in G[p]:
			if dist[i] == -1:
				dist[i] = dist[p] + 1
				q.append(i)
	return dist
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
dist = bfs()
(c1, c2) = (0, 0)
(group1, group2) = ([], [])
for i in range(1, n + 1):
	if dist[i] % 2 == 1:
		c1 += 1
		group1.append(i)
	else:
		c2 += 1
		group2.append(i)
m = n // 3
ans = [0] * (n + 1)
if m >= min(c1, c2):
	l = [3 * i + 3 for i in range(m)] + [3 * (i // 2) + i % 2 + 1 for i in range(n - m)]
	j = 0
	if c1 < c2:
		for i in group1:
			ans[i] = l[j]
			j += 1
		for i in group2:
			ans[i] = l[j]
			j += 1
	else:
		for i in group2:
			ans[i] = l[j]
			j += 1
		for i in group1:
			ans[i] = l[j]
			j += 1
else:
	j = 1
	for i in range(c1):
		if i <= (n - 1) // 3:
			ans[group1[i]] = 3 * i + 1
		else:
			ans[group1[i]] = 3 * j
			j += 1
	for i in range(c2):
		if i <= (n - 2) // 3:
			ans[group2[i]] = 3 * i + 2
		else:
			ans[group2[i]] = 3 * j
			j += 1
ans.pop(0)
print(*ans)


from collections import deque
n = int(input())
G = [[] for i in range(n)]
for i in range(1, n):
	(a, b) = map(lambda z: int(z) - 1, input().split())
	G[a].append(b)
	G[b].append(a)
color = [-1] * n
queue = deque([0])
color[0] = 0
red_blue = [1, 0]
while queue:
	now = queue.popleft()
	for to in G[now]:
		if color[to] == -1:
			color[to] = 1 - color[now]
			red_blue[color[to]] += 1
			queue.append(to)
ans = [-1] * n
if 3 * red_blue[0] < n:
	(one, two, three) = (0, 0, 0)
	for i in range(n):
		if color[i] == 0:
			ans[i] = 3 * three + 3
			three += 1
		elif 3 * one + 1 <= n:
			ans[i] = 3 * one + 1
			one += 1
		elif 3 * two + 2 <= n:
			ans[i] = 3 * two + 2
			two += 1
		else:
			ans[i] = 3 * three + 3
			three += 1
elif 3 * red_blue[1] < n:
	(one, two, three) = (0, 0, 0)
	for i in range(n):
		if color[i] == 1:
			ans[i] = 3 * three + 3
			three += 1
		elif 3 * one + 1 <= n:
			ans[i] = 3 * one + 1
			one += 1
		elif 3 * two + 2 <= n:
			ans[i] = 3 * two + 2
			two += 1
		else:
			ans[i] = 3 * three + 3
			three += 1
else:
	(one, two, three) = (0, 0, 0)
	for i in range(n):
		if color[i] == 0:
			if 3 * one + 1 <= n:
				ans[i] = 3 * one + 1
				one += 1
			else:
				ans[i] = 3 * three + 3
				three += 1
		elif 3 * two + 2 <= n:
			ans[i] = 3 * two + 2
			two += 1
		else:
			ans[i] = 3 * three + 3
			three += 1
print(*ans)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
lst = [[], [], []]
for i in range(1, n + 1):
	lst[i % 3].append(i)
p = [0] * n
depth = [-1] * n
depth[0] = 0
q = [0]
cnt = [1, 0]
while q:
	v = q.pop()
	for w in g[v]:
		if depth[w] != -1:
			continue
		depth[w] = depth[v] + 1
		cnt[depth[w] % 2] += 1
		q.append(w)
ans = [0] * n
if cnt[0] <= n // 3:
	ans[0] = lst[0].pop()
	q = [0]
	while q:
		v = q.pop()
		for w in g[v]:
			if ans[w] != 0:
				continue
			if depth[w] % 2 == 0:
				ans[w] = lst[0].pop()
			elif lst[1]:
				ans[w] = lst[1].pop()
			elif lst[2]:
				ans[w] = lst[2].pop()
			else:
				ans[w] = lst[0].pop()
			q.append(w)
elif cnt[1] <= n // 3:
	ans[0] = lst[1].pop()
	q = [0]
	while q:
		v = q.pop()
		for w in g[v]:
			if ans[w] != 0:
				continue
			if depth[w] % 2 != 0:
				ans[w] = lst[0].pop()
			elif lst[1]:
				ans[w] = lst[1].pop()
			elif lst[2]:
				ans[w] = lst[2].pop()
			else:
				ans[w] = lst[0].pop()
			q.append(w)
else:
	ans[0] = lst[2].pop()
	q = [0]
	while q:
		v = q.pop()
		for w in g[v]:
			if ans[w] != 0:
				continue
			if depth[w] % 2 != 0:
				if lst[1]:
					ans[w] = lst[1].pop()
				else:
					ans[w] = lst[0].pop()
			elif lst[2]:
				ans[w] = lst[2].pop()
			else:
				ans[w] = lst[0].pop()
			q.append(w)
print(*ans)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def eulerian_trail(tree, max_v, root=0):
	seen = [False] * (max_v + 1)
	trails = []
	depths = []
	weights = []
	stack = [(root, 0, 0, True)]
	while stack:
		(v, d, w, forward) = stack.pop()
		seen[v] = True
		trails.append(v)
		depths.append(d)
		weights.append(w)
		if not forward:
			continue
		for (u, w) in tree[v]:
			if not seen[u]:
				stack.append((v, d, -w, False))
				stack.append((u, d + 1, w, True))
	return (trails, depths, weights)
N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	graph[a].append((b, 1))
	graph[b].append((a, 1))
counts = [N // 3, (N + 2) // 3, (N + 1) // 3]
(vs, _, _) = eulerian_trail(graph, N - 1)
bp = [0] * N
for (i, v) in enumerate(vs):
	bp[v] = i & 1
ansmod = [-1] * N
if bp.count(0) <= counts[0]:
	for (v, b) in enumerate(bp):
		if b == 0 and counts[0] > 0:
			ansmod[v] = 0
			counts[0] -= 1
elif bp.count(1) <= counts[0]:
	for (v, b) in enumerate(bp):
		if b == 1 and counts[0] > 0:
			ansmod[v] = 0
			counts[0] -= 1
else:
	for (v, b) in enumerate(bp):
		if b == 0 and counts[1] > 0:
			ansmod[v] = 1
			counts[1] -= 1
		if b == 1 and counts[2] > 0:
			ansmod[v] = 2
			counts[2] -= 1
for v in range(N):
	if ansmod[v] < 0:
		for i in range(3):
			if counts[i] > 0:
				ansmod[v] = i
				counts[i] -= 1
				break
ans = []
M = [3, 1, 2]
for a in ansmod:
	ans.append(M[a])
	M[a] += 3
print(*ans)


def examA():
	S = SI()
	if len(S) % 2 == 1:
		print('No')
		return
	for i in range(len(S) // 2):
		if S[i * 2:i * 2 + 2] != 'hi':
			print('No')
			return
	print('Yes')
	return

def examB():
	(a, b, M) = LI()
	A = LI()
	B = LI()
	D = [LI() for _ in range(M)]
	ans = min(A) + min(B)
	for (x, y, c) in D:
		cur = A[x - 1] + B[y - 1] - c
		ans = min(ans, cur)
	print(ans)
	return

def examC():

	def bfs(n, e, fordfs):
		W = [-1] * n
		W[e] = 0
		que = deque()
		que.append(e)
		while que:
			now = que.popleft()
			nowW = W[now]
			for ne in fordfs[now]:
				if W[ne] == -1:
					W[ne] = nowW + 1
					que.append(ne)
		return W
	N = I()
	V = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = LI()
		a -= 1
		b -= 1
		V[a].append(b)
		V[b].append(a)
	L = bfs(N, 0, V)
	odd = 0
	for l in L:
		if l == -1:
			print(-1)
			return
		if l % 2 == 1:
			odd += 1
	G = []
	if odd * 2 < N:
		for i in range(N):
			if L[i] % 2 == 1:
				G.append(i)
	else:
		for i in range(N):
			if L[i] % 2 == 0:
				G.append(i)
	used = [False] * (N + 1)
	ans = [0] * N
	if N // 3 >= len(G):
		cur = 3
		for g in G:
			ans[g] = cur
			used[cur] = True
			cur += 3
		cur = 1
		for i in range(N):
			if ans[i] != 0:
				continue
			while used[cur]:
				cur += 1
			ans[i] = cur
			used[cur] = True
	else:
		cur = 1
		for g in G:
			ans[g] = cur
			used[cur] = True
			cur += 3
			if cur > N:
				cur = 3
		cur = 1
		for i in range(N):
			if ans[i] != 0:
				continue
			while used[cur]:
				cur += 1
			ans[i] = cur
			used[cur] = True
	print(' '.join(map(str, ans)))
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 6)
examC()


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def dfs(i, depth):
	visited[i] = True
	oe = depth % 2
	ans[i - 1] = oe
	count[oe] += 1
	nodes = tree[i]
	for node in nodes:
		if visited[node]:
			continue
		dfs(node, depth + 1)
N = int(input())
ans = [-1] * N
tree = [[] for i in range(N + 1)]
visited = [False] * (N + 1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a] += [b]
	tree[b] += [a]
dfs(1, 0)
even_len = count[0]
odd_len = count[1]
if even_len > N // 3 and odd_len > N // 3:
	for (i, oe) in enumerate(ans):
		if base[oe] > N:
			ans[i] = str(base[2])
			base[2] += 3
		else:
			ans[i] = str(base[oe])
			base[oe] += 3
elif even_len <= N // 3:
	for (i, oe) in enumerate(ans):
		if oe == 0:
			ans[i] = str(base[2])
			base[2] += 3
		elif base[0] <= N:
			ans[i] = str(base[0])
			base[0] += 3
		elif base[1] <= N:
			ans[i] = str(base[1])
			base[1] += 3
		else:
			ans[i] = str(base[2])
			base[2] += 3
elif odd_len <= N // 3:
	for (i, oe) in enumerate(ans):
		if oe == 1:
			ans[i] = str(base[2])
			base[2] += 3
		elif base[0] <= N:
			ans[i] = str(base[0])
			base[0] += 3
		elif base[1] <= N:
			ans[i] = str(base[1])
			base[1] += 3
		else:
			ans[i] = str(base[2])
			base[2] += 3
print(' '.join(ans))


from collections import deque

def main():
	N = int(input())
	adj = [set() for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].add(b - 1)
		adj[b - 1].add(a - 1)
	group = [set() for _ in range(2)]
	q = deque([(0, 0, -1)])
	while len(q):
		(cur, g, prev) = q.popleft()
		group[g].add(cur)
		for nxt in adj[cur]:
			if nxt == prev:
				continue
			q.append((nxt, 1 - g, cur))
	if len(group[0]) > len(group[1]):
		tmp = group[0]
		group[0] = group[1]
		group[1] = tmp
	ans = [0] * N
	pool = set(range(1, N + 1))
	if len(group[0]) <= N // 3:
		for (i, x) in enumerate(group[0]):
			ans[x] = (i + 1) * 3
			pool.remove((i + 1) * 3)
		for x in group[1]:
			ans[x] = pool.pop()
	else:
		cand = (list(range(1, N + 1, 3)) + list(range(3, N + 1, 3)))[:len(group[0])]
		for (x, v) in zip(group[0], cand):
			ans[x] = v
			pool.remove(v)
		for x in group[1]:
			ans[x] = pool.pop()
	print(*ans)
main()


N = int(input())
AB = [list(map(int, input().split())) for i in range(N - 1)]
c = [[] for i in range(N)]
v = [0] * N
x = [0] * N
for (i, j) in AB:
	c[i - 1].append(j - 1)
	c[j - 1].append(i - 1)
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(p):
	y = 1 if x[p] == 2 else 2
	for n in c[p]:
		if v[n] == 0:
			v[n] = 1
			x[n] = y
			dfs(n)
v[0] = x[0] = 1
dfs(0)

def f(x, a, b):
	(p, q, r) = (0, 0, 1)
	for i in range(N):
		if x[i] == a and p * 3 + 1 <= N:
			x[i] = p * 3 + 1
			p += 1
		elif x[i] == b and q * 3 + 2 <= N:
			x[i] = q * 3 + 2
			q += 1
		else:
			x[i] = r * 3
			r += 1
if x.count(1) <= N // 3:
	f(x, 2, 2)
elif x.count(2) <= N // 3:
	f(x, 1, 1)
else:
	f(x, 1, 2)
print(*x)


from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
edges = defaultdict(list)
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
colors = [-1] * n
colors[0] = 0
todo = []
for to in edges[0]:
	todo.append([to, 1])
while todo:
	(node, color) = todo.pop()
	if colors[node] != -1:
		continue
	colors[node] = color
	new_color = 1 - color
	for to in edges[node]:
		if colors[to] != -1:
			continue
		todo.append([to, new_color])
red_count = sum(colors)
blue_count = n - red_count
ans = [0] * n
num3s = list(range(3, n + 1, 3))
nums = [num for num in range(1, n + 1) if num % 3 != 0]
if red_count <= n // 3:
	for node in range(n):
		if colors[node] == 1:
			ans[node] = num3s.pop()
		else:
			if nums:
				num = nums.pop()
			else:
				num = num3s.pop()
			ans[node] = num
elif blue_count <= n // 3:
	for node in range(n):
		if colors[node] == 0:
			ans[node] = num3s.pop()
		else:
			if nums:
				num = nums.pop()
			else:
				num = num3s.pop()
			ans[node] = num
else:
	num1s = list(range(1, n + 1, 3))
	num2s = list(range(2, n + 1, 3))
	for node in range(n):
		if colors[node] == 1:
			if num1s:
				num = num1s.pop()
			else:
				num = num3s.pop()
			ans[node] = num
		else:
			if num2s:
				num = num2s.pop()
			else:
				num = num3s.pop()
			ans[node] = num
print(*ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
dist = [-1] * (N + 1)
stack = [1]
dist[1] = 0
while stack:
	v = stack.pop()
	for w in graph[v]:
		if dist[w] == -1:
			dist[w] = dist[v] + 1
			stack.append(w)
ev = [i for (i, x) in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for (i, x) in enumerate(dist) if x % 2 == 1 and i > 0]

def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
	assert len(ev) == x0 + x1 + x2
	assert len(od) == y0 + y1 + y2
	P = [0] * (N + 1)
	for i in ev:
		if x0:
			P[i] = (x0 + y0) * 3
			x0 -= 1
			continue
		if x1:
			P[i] = (x1 + y1) * 3 - 2
			x1 -= 1
			continue
		if x2:
			P[i] = (x2 + y2) * 3 - 1
			x2 -= 1
			continue
	for i in od:
		if y0:
			P[i] = (x0 + y0) * 3
			y0 -= 1
			continue
		if y1:
			P[i] = (x1 + y1) * 3 - 2
			y1 -= 1
			continue
		if y2:
			P[i] = (x2 + y2) * 3 - 1
			y2 -= 1
			continue
	return P[1:]

def solve(N, ev, od):
	x0 = N // 3
	x1 = (N + 2) // 3
	x2 = (N + 1) // 3
	perm = [0] * (N + 1)
	LE = len(ev)
	LO = len(od)
	if LE <= x0:
		return make_perm(N, ev, od, LE, 0, 0, x0 - LE, x1, x2)
	if LO <= x0:
		return make_perm(N, ev, od, x0 - LO, x1, x2, LO, 0, 0)
	if LE == x1:
		return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
	if LO == x1:
		return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
	return make_perm(N, ev, od, LE - x1, x1, 0, LO - x2, 0, x2)
P = solve(N, ev, od)
print(' '.join(map(str, P)))


import sys, collections as cl, bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10 ** 9 + 7
Max = sys.maxsize

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

def m():
	return map(int, input().split())

def onem():
	return int(input())

def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x) - 1):
		if aa != x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a

def jo(x):
	return ' '.join(map(str, x))

def max2(x):
	return max(map(max, x))

def In(x, a):
	k = bs.bisect_left(a, x)
	if k != len(a) and a[k] == x:
		return True
	else:
		return False
import collections
import itertools
import operator

class UnionFind:

	def __init__(self, x):

		class KeyDict(dict):

			def __missing__(self, key):
				self[key] = key
				return key
		self.parent = KeyDict()
		self.rank = collections.defaultdict(int)
		self.size = collections.defaultdict(lambda : 1)
		if x is not None:
			for elem in range(x + 1):
				(_, _, _) = (self.parent[elem], self.rank[elem], self.size[elem])

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if not self.are_same(x, y):
			xx = self.size[x]
			yy = self.size[y]
			if self.rank[x] < self.rank[y]:
				self.parent[x] = y
				self.size[y] += xx
			else:
				self.parent[y] = x
				self.size[x] += yy
		if self.rank[x] == self.rank[y]:
			self.rank[x] += 1

	def Size(self, x):
		return self.size[self.find(x)]

	def are_same(self, x, y):
		return self.find(x) == self.find(y)

	def grouper(self):
		roots = [(x, self.find(x_par)) for (x, x_par) in self.parent.items()]
		root = operator.itemgetter(1)
		for (_, group) in itertools.groupby(sorted(roots, key=root), root):
			yield [x for (x, _) in group]
n = onem()
tr = [[] for i in range(n)]
po = [0 for i in range(n)]
for i in range(n - 1):
	(a, b) = m()
	tr[a - 1].append(b - 1)
	tr[b - 1].append(a - 1)
de = cl.deque([[0, -1, 0]])
bl = 0
re = 0
while de:
	data = de.popleft()
	if data[2] % 2 == 0:
		po[data[0]] = 1
		re += 1
	else:
		po[data[0]] = 2
		bl += 1
	for i in range(len(tr[data[0]])):
		if tr[data[0]][i] != data[1]:
			de.append([tr[data[0]][i], data[0], data[2] + 1])
tr = n // 3
b0 = cl.deque([(i + 1) * 3 for i in range(tr)])
b1 = cl.deque([i * 3 + 1 for i in range(tr + (1 if n % 3 >= 1 else 0))])
b2 = cl.deque([i * 3 + 2 for i in range(tr + (1 if n % 3 >= 2 else 0))])
if re <= tr:
	for i in range(n):
		if po[i] == 1:
			po[i] = b0.popleft()
		elif len(b1) != 0:
			po[i] = b1.popleft()
		elif len(b2) != 0:
			po[i] = b2.popleft()
		else:
			po[i] = b0.popleft()
elif bl <= tr:
	for i in range(n):
		if po[i] == 2:
			po[i] = b0.popleft()
		elif len(b1) != 0:
			po[i] = b1.popleft()
		elif len(b2) != 0:
			po[i] = b2.popleft()
		else:
			po[i] = b0.popleft()
else:
	for i in range(n):
		if po[i] == 1:
			if len(b1) != 0:
				po[i] = b1.popleft()
			else:
				po[i] = b0.popleft()
		elif len(b2) != 0:
			po[i] = b2.popleft()
		else:
			po[i] = b0.popleft()
print(jo(po))


import math
import fractions

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def ValueToBits(x, digit):
	res = [0 for i in range(digit)]
	now = x
	for i in range(digit):
		res[i] = now % 2
		now = now >> 1
	return res

def BitsToValue(arr):
	n = len(arr)
	ans = 0
	for i in range(n):
		ans += arr[i] * 2 ** i
	return ans

def ValueToArray10(x, digit):
	ans = [0 for i in range(digit)]
	now = x
	for i in range(digit):
		ans[digit - i - 1] = now % 10
		now = now // 10
	return ans

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
n = int(input())
es = []
nb = [[] for i in range(n)]
for i in range(n - 1):
	(aa, bb) = list(map(int, input().split()))
	(a, b) = (aa - 1, bb - 1)
	nb[a].append(b)
	nb[b].append(a)
side = [[], []]
checked = [-1 for i in range(n)]
queue = [0]
side[0].append(0)
checked[0] = 0
fin = 0
while True:
	if len(queue) == fin:
		break
	seeing = queue[fin]
	fin += 1
	for j in range(len(nb[seeing])):
		nextval = nb[seeing][j]
		if checked[nextval] == -1:
			nextside = 1 - checked[seeing]
			checked[nextval] = nextside
			side[nextside].append(nextval)
			queue.append(nextval)
nums3 = [n // 3, n // 3, n // 3]
if n % 3 >= 1:
	nums3[0] += 1
if n % 3 == 2:
	nums3[1] += 1
ans = [-1 for i in range(n)]
if len(side[0]) <= nums3[2]:
	cou0 = len(side[0])
	cou1 = len(side[1])
	non3 = []
	for i in range(n):
		if (i + 1) % 3 != 0:
			non3.append(i + 1)
	for i in range(cou0):
		ans[side[0][i]] = 3 + 3 * i
	for j in range(nums3[2] - cou0):
		ans[side[1][j]] = 3 + 3 * (j + cou0)
	startnum = nums3[2] - cou0
	for j in range(cou1 - startnum):
		ans[side[1][startnum + j]] = non3[j]
elif len(side[1]) <= nums3[2]:
	cou0 = len(side[0])
	cou1 = len(side[1])
	non3 = []
	for i in range(n):
		if (i + 1) % 3 != 0:
			non3.append(i + 1)
	for i in range(cou1):
		ans[side[1][i]] = 3 + 3 * i
	for j in range(nums3[2] - cou1):
		ans[side[0][j]] = 3 + 3 * (j + cou1)
	startnum = nums3[2] - cou1
	for j in range(cou0 - startnum):
		ans[side[0][startnum + j]] = non3[j]
else:
	cou0 = len(side[0])
	cou1 = len(side[1])
	for i in range(nums3[0]):
		ans[side[0][i]] = 1 + 3 * i
	for i in range(nums3[1]):
		ans[side[1][i]] = 2 + 3 * i
	start0 = nums3[0]
	done0 = cou0 - nums3[0]
	start1 = nums3[1]
	done1 = cou1 - nums3[1]
	for i in range(done0):
		ans[side[0][start0 + i]] = 3 + 3 * i
	for i in range(done1):
		ans[side[1][start1 + i]] = 3 + 3 * (i + done0)
print(' '.join(map(str, ans)))


import sys
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	G[a].append(b)
	G[b].append(a)
group = [-1] * N
count = [0] * 2
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
	u = stack.pop()
	for v in G[u]:
		if group[v] == -1:
			group[v] = 1 - group[u]
			count[group[v]] += 1
			stack.append(v)
zeros = list(range(3, N + 1, 3))
ones = list(range(1, N + 1, 3))
twos = list(range(2, N + 1, 3))
ans = [0] * N
for g in range(2):
	if count[g] <= N // 3:
		for i in range(N):
			if group[i] == g:
				ans[i] = zeros.pop()
			elif len(twos) > 0:
				ans[i] = twos.pop()
			elif len(ones) > 0:
				ans[i] = ones.pop()
			else:
				ans[i] = zeros.pop()
		print(' '.join(map(str, ans)))
		exit()
for i in range(N):
	if group[i] == 0 and len(ones) > 0:
		ans[i] = ones.pop()
	elif group[i] == 1 and len(twos) > 0:
		ans[i] = twos.pop()
	else:
		ans[i] = zeros.pop()
print(' '.join(map(str, ans)))


import queue
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
num_0_mod_3 = n // 3
num_2_mod_3 = (n + 1) // 3
num_1_mod_3 = (n + 2) // 3

def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)
G = [[] for _ in range(n)]
for edge in edges:
	add_edge(edge[0] - 1, edge[1] - 1)
num_distance_even = 0
num_distance_odd = 0
q = queue.Queue()
q.put(0)
distance = [-1] * n
distance[0] = 0
num_distance_even += 1
for v in G[0]:
	q.put(v)
while q.qsize() > 0:
	now = q.get()
	for v in G[now]:
		if distance[v] >= 0:
			pass
		else:
			q.put(v)
			distance[v] = distance[now] + 1
			if distance[v] & 1:
				num_distance_odd += 1
			else:
				num_distance_even += 1
ans = [-1] * n
index_one = 1
index_two = 2
index_zero = 3
if num_distance_even >= num_1_mod_3 + num_2_mod_3:
	for i in range(n):
		if distance[i] & 1 == 1:
			ans[i] = index_zero
			index_zero += 3
		elif index_one <= n:
			ans[i] = index_one
			index_one += 3
		elif index_two <= n:
			ans[i] = index_two
			index_two += 3
		else:
			ans[i] = index_zero
			index_zero += 3
elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
	for i in range(n):
		if distance[i] & 1 == 0:
			ans[i] = index_zero
			index_zero += 3
		elif index_one <= n:
			ans[i] = index_one
			index_one += 3
		elif index_two <= n:
			ans[i] = index_two
			index_two += 3
		else:
			ans[i] = index_zero
			index_zero += 3
else:
	for i in range(n):
		if distance[i] & 1 == 1:
			if index_one <= n:
				ans[i] = index_one
				index_one += 3
			else:
				ans[i] = index_zero
				index_zero += 3
		elif index_two <= n:
			ans[i] = index_two
			index_two += 3
		else:
			ans[i] = index_zero
			index_zero += 3
print(' '.join(list(map(str, ans))))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

def main():
	n = int(input())
	tree = [[] for i in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		tree[a].append(b)
		tree[b].append(a)
	depth = [-1] * n
	depth[0] = 0

	def dfs(i):
		for e in tree[i]:
			if depth[e] == -1:
				depth[e] = (depth[i] + 1) % 2
				dfs(e)
	dfs(0)
	o = sum(depth)
	e = n - o
	if n % 3 == 0:
		i = n // 3
		j = i
		k = i
	elif n % 3 == 1:
		i = n // 3
		j = i + 1
		k = i
	else:
		i = n // 3
		j = i + 1
		k = j
	ans = [0] * n
	if 3 * e > n and 3 * o > n:
		for l in range(n):
			if depth[l] == 0:
				if j == 0:
					ans[l] = 3 * i
					i -= 1
				else:
					ans[l] = 3 * j - 2
					j -= 1
			elif k == 0:
				ans[l] = 3 * i
				i -= 1
			else:
				ans[l] = 3 * k - 1
				k -= 1
	elif 3 * e <= n:
		for l in range(n):
			if depth[l] == 0:
				ans[l] = 3 * i
				i -= 1
			elif j == 0 and k == 0:
				ans[l] = 3 * i
				i -= 1
			elif j == 0:
				ans[l] = 3 * k - 1
				k -= 1
			else:
				ans[l] = 3 * j - 2
				j -= 1
	else:
		for l in range(n):
			if depth[l] == 1:
				ans[l] = 3 * i
				i -= 1
			elif j == 0 and k == 0:
				ans[l] = 3 * i
				i -= 1
			elif j == 0:
				ans[l] = 3 * k - 1
				k -= 1
			else:
				ans[l] = 3 * j - 2
				j -= 1
	print(*ans)
main()


n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
	v = stack.pop()
	while edge[v]:
		u = edge[v].pop()
		if parent[v] != u:
			group[u] = not group[v]
			parent[u] = v
			stack.append(u)
three = 3
p = [0] * n
if group.count(False) <= n // 3:
	other = 1
	for i in range(n):
		if group[i] and other <= n:
			p[i] = other
			other += other % 3
		else:
			p[i] = three
			three += 3
elif group.count(True) <= n // 3:
	other = 1
	for i in range(n):
		if not group[i] and other <= n:
			p[i] = other
			other += other % 3
		else:
			p[i] = three
			three += 3
else:
	(one, two) = (1, 2)
	for i in range(n):
		if group[i] and one <= n:
			p[i] = one
			one += 3
		elif not group[i] and two <= n:
			p[i] = two
			two += 3
		else:
			p[i] = three
			three += 3
print(' '.join(map(str, p)))


import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for i in range(n - 1)]
b = [[] for i in range(n)]
a1 = []
a2 = []
ans = [0] * n
for i in range(n - 1):
	b[a[i][0] - 1].append(a[i][1] - 1)
	b[a[i][1] - 1].append(a[i][0] - 1)
import collections
from collections import deque

def tree(s):
	INF = -10 ** 9
	dis = [INF for i in range(n)]
	dis[s] = 0

	def bfs():
		d = deque()
		d.append(s)
		a1.append(s)
		while len(d):
			x = d.popleft()
			for i in range(len(b[x])):
				y = b[x][i]
				if dis[y] == INF:
					d.append(y)
					dis[y] = dis[x] + 1
					if dis[y] % 2 == 0:
						a1.append(y)
					else:
						a2.append(y)
		return (a1, a2)
	return bfs()
tree(0)
j = 0
k = 0
if min(len(a1), len(a2)) <= n // 3:
	if len(a1) <= n // 3:
		for i in range(1, n + 1):
			if i <= len(a1) * 3 and i % 3 == 0 and (j <= len(a1) - 1):
				ans[a1[j]] = i
				j += 1
			else:
				ans[a2[k]] = i
				k += 1
	else:
		for i in range(1, n + 1):
			if i <= len(a2) * 3 and i % 3 == 0 and (j <= len(a2) - 1):
				ans[a2[j]] = i
				j += 1
			else:
				ans[a1[k]] = i
				k += 1
else:
	for i in range(1, n + 1):
		if i % 3 == 1:
			ans[a1[j]] = i
			j += 1
		elif i % 3 == 2:
			ans[a2[k]] = i
			k += 1
		else:
			continue
	for i in range(3, n + 1, 3):
		if j <= len(a1) - 1:
			ans[a1[j]] = i
			j += 1
		else:
			ans[a2[k]] = i
			k += 1
print(*ans)


(n, *t) = map(int, open(0).read().split())
e = [[] for _ in range(n)]
x = [[], [], []]
for i in range(n):
	x[i % 3] += (i + 1,)
for (a, b) in zip(*[iter(t)] * 2):
	e[a - 1] += (b - 1,)
	e[b - 1] += (a - 1,)
a = [-1] * n
p = a[:]
p[0] = 0
s = [0]
c = [1, 0]
while s:
	v = s.pop()
	for w in e[v]:
		if p[w] < 0:
			p[w] = p[v] ^ 1
			c[p[w]] += 1
			s += (w,)
if min(c) <= n // 3:
	x[0] += x[1]
	f = c[0] <= n // 3
	for (i, v) in enumerate(p):
		j = (v == f) - 1
		a[i] = x[j if x[j] else -1].pop()
else:
	for (i, v) in enumerate(p):
		a[i] = x[v if x[v] else -1].pop()
print(*a)


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import queue

def getlist():
	return list(map(int, input().split()))
INF = float('inf')

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):

	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ['No'] * N
		self.visit[s] = 'Yes'
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == 'No':
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = 'Yes'

def main():
	N = int(input())
	a0 = int(N // 3)
	a1 = int((N + 2) // 3)
	a2 = int((N + 1) // 3)
	G = Graph()
	for i in range(N - 1):
		(a, b) = getlist()
		a -= 1
		b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
	BF = BFS(G, 0, N)
	dist = BF.dist
	dis_even = 0
	dis_odd = 0
	for i in range(N):
		if dist[i] % 2 == 0:
			dis_even += 1
		else:
			dis_odd += 1
	ans = [0] * N
	judge = 'No'
	S = [(i + 1) * 3 for i in range(a0)] + [i * 3 + 1 for i in range(a1)] + [i * 3 + 2 for i in range(a2)]
	if a2 <= dis_odd and a1 <= dis_even:
		judge = 'Yes'
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a2:
					ans[i] = c1 * 3 + 2
					c1 += 1
			elif c2 < a1:
				ans[i] = c2 * 3 + 1
				c2 += 1
		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1
		print(' '.join(map(str, ans)))
	elif a1 <= dis_odd and a2 <= dis_even:
		judge = 'Yes'
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a1:
					ans[i] = c1 * 3 + 2
					c1 += 1
			elif c2 < a2:
				ans[i] = c2 * 3 + 1
				c2 += 1
		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1
		print(' '.join(map(str, ans)))
	elif dis_odd <= a0:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1
		print(' '.join(map(str, ans)))
	else:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 == 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1
		print(' '.join(map(str, ans)))
main()


import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, readline().split())
	g[a].append(b)
	g[b].append(a)
colors = [0] * (n + 1)
colors[1] = 1
todo = []
for to in g[1]:
	todo.append([to, -1])
while todo:
	(node, color) = todo.pop()
	if colors[node] != 0:
		continue
	colors[node] = color
	new_color = -color
	for to in g[node]:
		if colors[to] != 0:
			continue
		todo.append([to, new_color])
ans = [0] * (n + 1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1, n + 1):
	if i % 3 == 1:
		t1.append(i)
	elif i % 3 == 2:
		t2.append(i)
	else:
		t0.append(i)
black = 0
for i in colors[1:]:
	if i == 1:
		black += 1
if black <= n // 3:
	for i in range(1, n + 1):
		if colors[i] == 1:
			ans[i] = t0.pop()
		elif t1:
			ans[i] = t1.pop()
		elif t2:
			ans[i] = t2.pop()
		else:
			ans[i] = t0.pop()
elif black >= n - n // 3:
	for i in range(1, n + 1):
		if colors[i] == -1:
			ans[i] = t0.pop()
		elif t1:
			ans[i] = t1.pop()
		elif t2:
			ans[i] = t2.pop()
		else:
			ans[i] = t0.pop()
else:
	for i in range(1, n + 1):
		if colors[i] == 1:
			if t1:
				ans[i] = t1.pop()
			else:
				ans[i] = t0.pop()
		elif t2:
			ans[i] = t2.pop()
		else:
			ans[i] = t0.pop()
print(*ans[1:])


from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
Q = deque([0])
R = []
DE = [0] * N
e = 1
o = 0
while Q:
	i = deque.popleft(Q)
	R.append(i)
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			DE[a] = DE[i] ^ 1
			if DE[a]:
				o += 1
			else:
				e += 1
			X[a].remove(i)
			deque.append(Q, a)
A = [i for i in range(1, N + 1) if i % 3 == 1]
B = [i for i in range(1, N + 1) if i % 3 == 2]
C = [i for i in range(1, N + 1) if i % 3 == 0]
ANS = [-1] * N
if e <= len(C):
	for i in range(N):
		if DE[i] == 0:
			ANS[i] = C.pop()
	for i in range(N):
		if ANS[i] < 0:
			ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
elif o <= len(C):
	for i in range(N):
		if DE[i] == 1:
			ANS[i] = C.pop()
	for i in range(N):
		if ANS[i] < 0:
			ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
else:
	for i in range(N):
		if DE[i] == 0:
			ANS[i] = A.pop()
			if len(A) == 0:
				break
	for i in range(N):
		if DE[i] == 1:
			ANS[i] = B.pop()
			if len(B) == 0:
				break
	for i in range(N):
		if ANS[i] < 0:
			ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
print(*ANS)


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)
q = deque([0])
depth = [-1] * n
depth[0] = 0
d = 1
while q:
	x = q.popleft()
	d = depth[x] + 1
	for y in G[x]:
		if depth[y] == -1:
			q.append(y)
			depth[y] = d
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, 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]
if len(even) <= n // 3:
	(odd, even) = (even, odd)
if len(odd) <= n // 3:
	r = r2 + r1 + r0
else:
	r = r1 + r0 + r2
ans = [0] * n
for i in odd:
	ans[i] = r.pop()
for i in even:
	ans[i] = r.pop()
print(*ans)


from collections import deque
N = int(input())
tree = [[0, 0] for _ in range(N + 1)]
edge = [set() for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a].add(b)
	edge[b].add(a)
queue = deque([1])
(d, even_or_odd) = (1, [1, 0])
while len(queue) > 0:
	newq = set()
	for _ in range(len(queue)):
		p = queue.pop()
		for q in edge[p]:
			if q != tree[p][0]:
				newq.add(q)
				(tree[q][0], tree[q][1]) = (p, d % 2)
	even_or_odd[d % 2] += len(newq)
	d += 1
	queue = deque(list(newq))
stock = [N // 3] * 3
for i in range(N % 3):
	stock[i] += 1
if min(even_or_odd) > N // 3:
	(i, j, k, ans) = (0, 0, 1, [])
	for l in range(1, N + 1):
		if tree[l][1] == 0 and i <= stock[0] - 1:
			ans.append(3 * i + 1)
			i += 1
		elif tree[l][1] != 0 and j <= stock[1] - 1:
			ans.append(3 * j + 2)
			j += 1
		else:
			ans.append(3 * k)
			k += 1
elif even_or_odd[0] <= stock[0] - 1:
	(ans, num) = ([], [3 * i for i in range(1, N // 3 + 1)] + [i for i in range(N + 1) if i % 3 != 0])
	(i, j) = (0, -1)
	for k in range(1, N + 1):
		if tree[k][1] == 0:
			ans.append(num[i])
			i += 1
		else:
			ans.append(num[j])
			j -= 1
else:
	(ans, num) = ([], [3 * i for i in range(1, N // 3 + 1)] + [i for i in range(N + 1) if i % 3 != 0])
	(i, j) = (0, -1)
	for k in range(1, N + 1):
		if tree[k][1] != 0:
			ans.append(num[i])
			i += 1
		else:
			ans.append(num[j])
			j -= 1
print(' '.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read
(n, *ab) = [int(i) - 1 for i in read().split()]
n += 1
mp = iter(ab)
g = [[] for _ in range(n)]
for (a, b) in zip(mp, mp):
	g[a].append(b)
	g[b].append(a)
q = [0]
parent = [-1] * n
depth = [0] * n
while q:
	v = q.pop()
	d = depth[v]
	for c in g[v]:
		if c != parent[v]:
			q.append(c)
			parent[c] = v
			depth[c] = d + 1
odd = [i for (i, d) in enumerate(depth) if d & 1]
even = [i for (i, d) in enumerate(depth) if d & 1 == 0]
s0 = list(range(3, n + 1, 3))
s1 = list(range(1, n + 1, 3))
s2 = list(range(2, n + 1, 3))
ans = [0] * n
m = n // 3
if len(even) <= m:
	(odd, even) = (even, odd)
if len(odd) <= m:
	s2 += s1 + s0
else:
	s2 += s0 + s1
for i in odd:
	ans[i] = s2.pop()
for i in even:
	ans[i] = s2.pop()
print(*ans)


def main():
	from collections import deque
	from itertools import chain
	import sys
	input = sys.stdin.readline
	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)
	dq = deque([0])
	parity = [-1] * N
	parity[0] = 0
	size_0 = 0
	while dq:
		v = dq.popleft()
		p = parity[v]
		if p == 0:
			size_0 += 1
		np = 1 ^ p
		for u in graph[v]:
			if ~parity[u]:
				continue
			parity[u] = np
			dq.append(u)
	k = N // 3
	g1 = iter(range(1, N + 1, 3))
	g2 = iter(range(2, N + 1, 3))
	g3 = iter(range(3, N + 1, 3))
	if size_0 <= k:
		g123 = chain(g1, g2, g3)
		ret = (next(g3) if p == 0 else next(g123) for p in parity)
	elif N - size_0 <= k:
		g123 = chain(g1, g2, g3)
		ret = (next(g3) if p == 1 else next(g123) for p in parity)
	else:
		g13 = chain(g1, g3)
		g23 = chain(g2, g3)
		ret = (next(g13) if p == 0 else next(g23) for p in parity)
	print(*ret)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	vec[a - 1].append(b - 1)
	vec[b - 1].append(a - 1)
q = [(0, -1, 0)]
dist = [0] * N
cnt = [0, 0]
while q:
	(cur, pre, cost) = q.pop()
	dist[cur] = cost
	cnt[cost] += 1
	for nex in vec[cur]:
		if nex != pre:
			q.append((nex, cur, cost ^ 1))
one = 1
two = 2
three = 3
if cnt[0] < (N + 2) // 3:
	for i in range(N):
		if dist[i] == 0:
			dist[i] = three
			three += 3
		elif one <= N:
			dist[i] = one
			one += 3
		elif two <= N:
			dist[i] = two
			two += 3
		else:
			dist[i] = three
			three += 3
elif cnt[1] < (N + 1) // 3:
	for i in range(N):
		if dist[i] == 1:
			dist[i] = three
			three += 3
		elif one <= N:
			dist[i] = one
			one += 3
		elif two <= N:
			dist[i] = two
			two += 3
		else:
			dist[i] = three
			three += 3
else:
	for i in range(N):
		if dist[i] == 0 and one <= N:
			dist[i] = one
			one += 3
		elif dist[i] == 1 and two <= N:
			dist[i] = two
			two += 3
		else:
			dist[i] = three
			three += 3
print(*dist)


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

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

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return input().split()

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():

	def f(point, pre):
		p = lis[point]
		for nex in edg[point]:
			if nex == pre:
				continue
			lis[nex] = p + 1
			f(nex, point)
		return
	n = II()
	ab = LIR_(n - 1)
	lis = [-1] * n
	edg = [[] for _ in range(n)]
	for (a, b) in ab:
		edg[a].append(b)
		edg[b].append(a)
	lis[0] = 1
	f(0, -1)
	d = [0, 0]
	for i in lis:
		d[i & 1] += 1
	ans = [None] * n
	if d[0] <= n // 3:
		t = 1
		for i in range(n):
			if lis[i] & 1:
				continue
			ans[i] = str(t * 3)
			t += 1
		m = t * 3
		t = 1
		for i in range(n):
			if ans[i]:
				continue
			ans[i] = str(t)
			t += 1
			if t >= m:
				continue
			if t % 3 == 0:
				t += 1
	elif d[1] <= n // 3:
		t = 1
		for i in range(n):
			if not lis[i] & 1:
				continue
			ans[i] = str(t * 3)
			t += 1
		m = t * 3
		t = 1
		for i in range(n):
			if ans[i]:
				continue
			ans[i] = str(t)
			t += 1
			if t >= m:
				continue
			if t % 3 == 0:
				t += 1
	else:
		t = n // 3
		odd = 1
		even = 2
		for i in range(n):
			if t:
				if lis[i] & 1:
					if d[1] <= n // 3 + (n % 3 >= 1):
						ans[i] = str(odd)
						odd += 3
					else:
						ans[i] = str(3 * t)
						t -= 1
						d[1] -= 1
				elif d[0] <= n // 3 + (n % 3 >= 2):
					ans[i] = str(even)
					even += 3
				else:
					ans[i] = str(3 * t)
					t -= 1
					d[0] -= 1
			elif lis[i] & 1:
				ans[i] = str(odd)
				odd += 3
			else:
				ans[i] = str(even)
				even += 3
	print(' '.join(ans))
	return
solve()


import sys
input = sys.stdin.buffer.readline
N = int(input())
tree = [[] for _ in range(N)]
bip = [None for _ in range(N)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	tree[u - 1].append(v - 1)
	tree[v - 1].append(u - 1)
stack = [0]
bip[0] = 0
while stack:
	node = stack.pop()
	for adj in tree[node]:
		if bip[adj] is not None:
			continue
		bip[adj] = not bip[node]
		stack.append(adj)
res = [None for _ in range(N)]
white = sum(bip)
black = N - white
p0 = []
p1 = []
p2 = []
for i in range(1, N + 1):
	if i % 3 == 0:
		p0.append(i)
for i in range(1, N + 1):
	if i % 3 == 1:
		p1.append(i)
for i in range(1, N + 1):
	if i % 3 == 2:
		p2.append(i)
if white <= N // 3:
	p = p0 + p1 + p2
	cnt = 0
	for i in range(N):
		if bip[i]:
			res[i] = p[cnt]
			cnt += 1
	for i in range(N):
		if not bip[i]:
			res[i] = p[cnt]
			cnt += 1
	print(*res)
elif black <= N // 3:
	p = p0 + p1 + p2
	cnt = 0
	for i in range(N):
		if not bip[i]:
			res[i] = p[cnt]
			cnt += 1
	for i in range(N):
		if bip[i]:
			res[i] = p[cnt]
			cnt += 1
	print(*res)
else:
	p = p1 + p0 + p2
	cnt = 0
	for i in range(N):
		if not bip[i]:
			res[i] = p[cnt]
			cnt += 1
	for i in range(N):
		if bip[i]:
			res[i] = p[cnt]
			cnt += 1
	print(*res)


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)
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()
		elif 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()
		elif 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()
		elif len(q1) > 0:
			res[i] = q1.popleft()
		elif len(q2) > 0:
			res[i] = q2.popleft()
		else:
			res[i] = q0.popleft()
print_l(res)


N = int(input())
data = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	data[a].append(b)
	data[b].append(a)
stack = [0]
d = [-1] * N
d[0] = 0
while stack:
	x = stack.pop()
	for y in data[x]:
		if d[y] != -1:
			continue
		d[y] = d[x] + 1
		stack.append(y)
mod = [[], []]
for i in range(N):
	mod[d[i] % 2].append(i)
ans = [0] * N
p = 1
q = 2
r = 3
if len(mod[0]) > N // 3 and len(mod[1]) > N // 3:
	for k in mod[0]:
		if p <= N:
			ans[k] = p
			p += 3
		else:
			ans[k] = r
			r += 3
	for l in mod[1]:
		if q <= N:
			ans[l] = q
			q += 3
		else:
			ans[l] = r
			r += 3
elif len(mod[0]) > N // 3:
	for k in mod[0]:
		if p <= N:
			ans[k] = p
			p += 3
		elif q <= N:
			ans[k] = q
			q += 3
		else:
			ans[k] = r
			r += 3
	for l in mod[1]:
		ans[l] = r
		r += 3
else:
	for k in mod[1]:
		if p <= N:
			ans[k] = p
			p += 3
		elif q <= N:
			ans[k] = q
			q += 3
		else:
			ans[k] = r
			r += 3
	for l in mod[0]:
		ans[l] = r
		r += 3
print(' '.join(map(str, ans)))


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
N = ir()
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = lr()
	graph[a].append(b)
	graph[b].append(a)
root = 1
rank = [0] * (N + 1)
rank[1] = 1
parent = [0] * (N + 1)
stack = [root]
while stack:
	cur = stack.pop()
	r = rank[cur]
	for next in graph[cur]:
		if next == parent[cur]:
			continue
		parent[next] = cur
		rank[next] = r + 1
		stack.append(next)
counter = [0, 0]
for x in rank[1:]:
	counter[x % 2] += 1
num0mod3 = N // 2
num1mod3 = (N + 2) // 3
num2mod3 = (N + 1) // 3
answer = [0] * (N + 1)
if max(counter) >= num1mod3 + num2mod3:
	if counter[0] > counter[1]:
		index = 0
	else:
		index = 1
	cur = 1
	used = set()
	for i in range(1, N + 1):
		if rank[i] % 2 == index:
			answer[i] = cur
			used.add(cur)
			cur += 1
			if cur % 3 == 0:
				cur += 1
			if cur > N:
				break
	cur = 1
	for j in range(1, N + 1):
		while cur in used:
			cur += 1
		if answer[j] == 0:
			answer[j] = cur
			used.add(cur)
else:
	if counter[0] > counter[1]:
		index = 0
	else:
		index = 1
	cur = 1
	used = set()
	for i in range(1, N + 1):
		if rank[i] % 2 == index:
			answer[i] = cur
			used.add(cur)
			cur += 3
			if cur > N:
				break
	cur = 2
	for i in range(1, N + 1):
		if rank[i] % 2 == 1 - index:
			answer[i] = cur
			used.add(cur)
			cur += 3
			if cur > N:
				break
	cur = 1
	for j in range(1, N + 1):
		while cur in used:
			cur += 1
		if answer[j] == 0:
			answer[j] = cur
			used.add(cur)
print(*answer[1:])


from collections import deque
import math
N = int(input())
side = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	side[a - 1].append(b - 1)
	side[b - 1].append(a - 1)
ans = [0] * N
ans[0] = 1
queue = deque([0])
count = [0, 1, 0]
while queue:
	q = queue.popleft()
	for i in side[q]:
		if ans[i] == 0:
			ans[i] = ans[q] % 2 + 1
			count[ans[i]] += 1
			queue.append(i)
if max(count) <= N - (N + 1) // 3:
	X = [3, 2, 2]
	X[count.index(max(count))] = 1
	for i in range(N):
		if X[ans[i]] <= N:
			X[ans[i]] += 3
			ans[i] = X[ans[i]] - 3
		else:
			ans[i] = X[0]
			X[0] += 3
else:
	Y = 3 - count.index(max(count))
	Z = 3 - Y
	X = 3
	for i in range(N):
		if ans[i] == Y:
			ans[i] = X
			X += 3
	W = 1
	for i in range(N):
		if ans[i] == Z:
			ans[i] = W
			W += 1
			if W % 3 == 0 and W < X:
				W += 1
print(*ans)


import sys
input = sys.stdin.readline
from collections import *

def bfs():
	color = [0] * N
	color[0] = 1
	q = deque([0])
	while q:
		v = q.popleft()
		for nv in G[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
	return color
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
n = [0, 0, 0]
for i in range(1, N + 1):
	n[i % 3] += 1
color = bfs()
b = color.count(1)
if b > N - b:
	for i in range(N):
		color[i] *= -1
ans = [-1] * N
if min(b, N - b) <= n[0]:
	q = deque([i for i in range(1, N + 1) if i % 3 == 0] + [i for i in range(1, N + 1) if i % 3 != 0])
else:
	q = deque([i for i in range(1, N + 1) if i % 3 == 1] + [i for i in range(1, N + 1) if i % 3 == 0] + [i for i in range(1, N + 1) if i % 3 == 2])
for i in range(N):
	if color[i] == 1:
		ans[i] = q.popleft()
for i in range(N):
	if color[i] == -1:
		ans[i] = q.popleft()
print(*ans)


from heapq import heappop as he
n = int(input())
s = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	s[a].append(b)
	s[b].append(a)
c = [0] * n
q = [1]
t = [1] * n
t[1] = 0
fl = 0
while q:
	fl ^= 1
	p = []
	for j in q:
		for h in s[j]:
			if t[h]:
				t[h] = 0
				c[h] = fl
				p.append(h)
	q = p.copy()
if c.count(1) > n // 3 and c.count(0) > n // 3:
	(p, q, r) = (1, 2, 3)
	for i in range(n):
		if c[i]:
			if q <= n:
				c[i] = q
				q += 3
			else:
				c[i] = r
				r += 3
		elif p <= n:
			c[i] = p
			p += 3
		else:
			c[i] = r
			r += 3
elif c.count(1) <= n // 3:
	(p, q, r) = (1, 2, 3)
	for i in range(n):
		if c[i]:
			c[i] = r
			r += 3
		elif p <= n:
			c[i] = p
			p += 3
		elif q <= n:
			c[i] = q
			q += 3
		else:
			c[i] = r
			r += 3
else:
	(p, q, r) = (1, 2, 3)
	for i in range(n):
		if not c[i]:
			c[i] = r
			r += 3
		elif q <= n:
			c[i] = q
			q += 3
		elif p <= n:
			c[i] = p
			p += 3
		else:
			c[i] = r
			r += 3
print(*c)


from collections import deque
n = int(input())
graph = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
even = []
odd = []
ansl = [0] * n
nums = set([i for i in range(1, n + 1)])
dist = [-1] * n
dist[0] = 0
even.append(0)
D = deque([0])
while D:
	v = D.popleft()
	for i in graph[v]:
		if dist[i] != -1:
			continue
		dist[i] = dist[v] + 1
		D.append(i)
		if dist[i] % 2:
			odd.append(i)
		else:
			even.append(i)
El = len(even)
Ol = len(odd)
if El <= Ol:
	if El <= n // 3:
		for i in range(El):
			ansl[even[i]] = (i + 1) * 3
			nums.remove((i + 1) * 3)
		for i in range(Ol):
			ansl[odd[i]] = nums.pop()
	else:
		cnt = 0
		while 3 * cnt + 2 <= n:
			ansl[even[cnt]] = 3 * cnt + 2
			ansl[odd[cnt]] = 3 * cnt + 1
			nums.remove(3 * cnt + 2)
			nums.remove(3 * cnt + 1)
			cnt += 1
		for i in range(cnt, El):
			ansl[even[i]] = nums.pop()
		for i in range(cnt, Ol):
			ansl[odd[i]] = nums.pop()
if Ol < El:
	if Ol <= n // 3:
		for i in range(Ol):
			ansl[odd[i]] = (i + 1) * 3
			nums.remove((i + 1) * 3)
		for i in range(El):
			ansl[even[i]] = nums.pop()
	else:
		cnt = 0
		while 3 * cnt + 2 <= n:
			ansl[odd[cnt]] = 3 * cnt + 2
			ansl[even[cnt]] = 3 * cnt + 1
			nums.remove(3 * cnt + 2)
			nums.remove(3 * cnt + 1)
			cnt += 1
		for i in range(cnt, Ol):
			ansl[odd[i]] = nums.pop()
		for i in range(cnt, El):
			ansl[even[i]] = nums.pop()
print(*ansl)


import sys
input = sys.stdin.readline
from collections import deque

def main():
	n = int(input())
	Edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		Edges[a].append(b)
		Edges[b].append(a)
	Depth = [-1] * n
	Depth[0] = 0
	q = deque()
	q.append(0)
	while q:
		fr = q.popleft()
		for to in Edges[fr]:
			if Depth[to] == -1:
				Depth[to] = Depth[fr] + 1
				q.append(to)
	Group = [[] for _ in range(2)]
	for i in range(n):
		Group[Depth[i] % 2].append(i)
	(l_even, l_odd) = (len(Group[0]), len(Group[1]))
	Ans = [0] * n
	Used = [False] * (n + 1)
	if l_even <= l_odd:
		if l_even <= n // 3:
			tmp_3 = 3
			tmp_others = 1
			for i in Group[0]:
				Ans[i] = tmp_3
				Used[tmp_3] = True
				tmp_3 += 3
			for i in Group[1]:
				while Used[tmp_others]:
					tmp_others += 1
				Ans[i] = tmp_others
				Used[tmp_others] = True
			return Ans
	elif l_odd <= n // 3:
		tmp_3 = 3
		tmp_others = 1
		for i in Group[1]:
			Ans[i] = tmp_3
			Used[tmp_3] = True
			tmp_3 += 3
		for i in Group[0]:
			while Used[tmp_others]:
				tmp_others += 1
			Ans[i] = tmp_others
			Used[tmp_others] = True
		return Ans
	tmp_even = 1
	tmp_odd = 2
	tmp_others = 3
	for i in Group[0]:
		if tmp_even <= n:
			Ans[i] = tmp_even
			tmp_even += 3
		else:
			Ans[i] = tmp_others
			tmp_others += 3
	for i in Group[1]:
		if tmp_odd <= n:
			Ans[i] = tmp_odd
			tmp_odd += 3
		else:
			Ans[i] = tmp_others
			tmp_others += 3
	return Ans
Ans = main()
print(*Ans)


from collections import defaultdict, Counter, deque
(N,) = list(map(int, input().split()))
g = defaultdict(list)
for i in range(N - 1):
	(u, v) = list(map(int, input().split()))
	g[u].append(v)
	g[v].append(u)
source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 0
while q:
	node = q.popleft()
	level = dist[node]
	for nbr in g[node]:
		if nbr not in dist:
			q.append(nbr)
			dist[nbr] = level + 1
mod1 = list(range(1, N + 1, 3))
mod2 = list(range(2, N + 1, 3))
mod0 = list(range(3, N + 1, 3))
parityCounts = Counter((level % 2 for level in dist.values()))
assign = {}
if min(parityCounts[0], parityCounts[1]) <= len(mod0):
	parityOfSmaller = min([0, 1], key=lambda k: parityCounts[k])
	for i in range(1, N + 1):
		if dist[i] % 2 == parityOfSmaller:
			assign[i] = mod0.pop()
		elif mod1:
			assign[i] = mod1.pop()
		elif mod2:
			assign[i] = mod2.pop()
		elif mod0:
			assign[i] = mod0.pop()
else:
	assert len(mod0) <= len(mod2) <= len(mod1)
	if parityCounts[0] < parityCounts[1]:
		assert len(mod2) <= parityCounts[0]
		assert len(mod1) <= parityCounts[1]
		parityToMod = {0: mod2, 1: mod1}
	else:
		assert len(mod1) <= parityCounts[0]
		assert len(mod2) <= parityCounts[1]
		parityToMod = {0: mod1, 1: mod2}
	for i in range(1, N + 1):
		mod = parityToMod[dist[i] % 2]
		if mod:
			assign[i] = mod.pop()
		else:
			assign[i] = mod0.pop()
print(' '.join((str(assign[i]) for i in range(1, N + 1))))


import collections
import sys
sys.setrecursionlimit(2 * 10 ** 5)
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for (a, b) in zip(AB[::2], AB[1::2]):
	G[a].add(b)
	G[b].add(a)
color = [None] * (N + 1)

def dfs(G, v, cur):
	color[v] = cur
	for w in G[v]:
		if color[w] is None:
			dfs(G, w, 1 - cur)
dfs(G, 1, 0)
c = collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))
(i0, i1) = (0, 1)
if c[0] > c[1]:
	(i0, i1) = (1, 0)
ans = [None] * (N + 1)
if c[i0] <= len(cand3):
	for i in range(1, N + 1):
		if color[i] == i0:
			ans[i] = cand3.pop()
		elif cand1:
			ans[i] = cand1.pop()
		elif cand2:
			ans[i] = cand2.pop()
		elif cand3:
			ans[i] = cand3.pop()
else:
	for i in range(1, N + 1):
		if color[i] == i0:
			if cand2:
				ans[i] = cand2.pop()
			elif cand3:
				ans[i] = cand3.pop()
		elif cand1:
			ans[i] = cand1.pop()
		elif cand3:
			ans[i] = cand3.pop()
print(*ans[1:])


from collections import deque

def main():
	N = int(input())
	g = {}
	for i in range(N):
		g[i] = set()
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		g[a - 1].add(b - 1)
		g[b - 1].add(a - 1)
	dist = [-1] * N
	dist[0] = 0
	n_even = 0
	que = deque([0])
	while len(que):
		v = que[0]
		if dist[v] % 2 == 0:
			n_even += 1
		que.popleft()
		for n in g[v]:
			if dist[n] == -1:
				dist[n] = (dist[v] + 1) % 2
				que.append(n)
	ans = [-1] * N
	if n_even <= int(N / 3):
		(n3, n3q, n3r) = (1, 0, 1)
		for i in range(N):
			if dist[i] == 0:
				ans[i] = n3 * 3
				n3 += 1
			elif n3q * 3 + n3r <= N:
				ans[i] = n3q * 3 + n3r
				if n3r == 1:
					n3r = 2
				else:
					n3q += 1
					n3r = 1
			else:
				ans[i] = n3 * 3
				n3 += 1
	elif n_even > int(N * 2 / 3):
		(n3, n3q, n3r) = (1, 0, 1)
		for i in range(N):
			if dist[i] == 1:
				ans[i] = n3 * 3
				n3 += 1
			elif n3q * 3 + n3r <= N:
				ans[i] = n3q * 3 + n3r
				if n3r == 1:
					n3r = 2
				else:
					n3q += 1
					n3r = 1
			else:
				ans[i] = n3 * 3
				n3 += 1
	else:
		(n3, n31, n32) = (1, 0, 0)
		for i in range(N):
			if dist[i] == 0:
				if n31 * 3 + 1 <= N:
					ans[i] = n31 * 3 + 1
					n31 += 1
				else:
					ans[i] = n3 * 3
					n3 += 1
			elif n32 * 3 + 2 <= N:
				ans[i] = n32 * 3 + 2
				n32 += 1
			else:
				ans[i] = n3 * 3
				n3 += 1
	print(' '.join(map(str, ans)))
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(nodes, src):
	N = len(nodes)
	stack = [(src, -1, 0)]
	dist = [-1] * N
	while stack:
		(u, prev, c) = stack.pop()
		dist[u] = c
		for v in nodes[u]:
			if v != prev:
				stack.append((v, u, 1 - c))
	return dist
N = INT()
nodes = [[] for i in range(N)]
for _ in range(N - 1):
	(a, b) = MAP()
	a -= 1
	b -= 1
	nodes[a].append(b)
	nodes[b].append(a)
res = dfs(nodes, 0)
cnt0 = res.count(0)
cnt1 = res.count(1)
ans = [0] * N
if cnt0 <= N // 3 or cnt1 <= N // 3:
	if cnt0 > cnt1:
		(cnt0, cnt1) = (cnt1, cnt0)
		res = [1 - c for c in res]
	p1 = 1
	p2 = 2
	p3 = 3
	for i in range(N):
		if res[i] == 0:
			ans[i] = p3
			p3 += 3
		elif p1 <= N:
			ans[i] = p1
			p1 += 3
		elif p2 <= N:
			ans[i] = p2
			p2 += 3
		else:
			ans[i] = p3
			p3 += 3
else:
	p1 = 1
	p2 = 2
	p3 = 3
	for i in range(N):
		if res[i] == 0:
			if p1 <= N:
				ans[i] = p1
				p1 += 3
			else:
				ans[i] = p3
				p3 += 3
		elif p2 <= N:
			ans[i] = p2
			p2 += 3
		else:
			ans[i] = p3
			p3 += 3
print(*ans)


import sys
sys.setrecursionlimit(10 ** 9)
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)

def dfs(u, par, depth):
	dist_list[u] = depth
	for v in tree[u]:
		if v != par:
			dfs(v, u, depth + 1)
dist_list = [-1] * (N + 1)
dfs(1, 0, 0)
num_even = num_odd = 0
for i in range(1, N + 1):
	if dist_list[i] % 2 == 0:
		num_even += 1
	else:
		num_odd += 1
num_3m0 = 3
num_3m1 = 1
num_3m2 = 2
answer_list = [0] * (N + 1)
if num_even <= N // 3:
	for i in range(1, N + 1):
		if dist_list[i] % 2 == 0:
			answer_list[i] = num_3m0
			num_3m0 += 3
		elif num_3m1 <= N:
			answer_list[i] = num_3m1
			num_3m1 += 3
		elif num_3m2 <= N:
			answer_list[i] = num_3m2
			num_3m2 += 3
		else:
			answer_list[i] = num_3m0
			num_3m0 += 3
elif num_odd <= N // 3:
	for i in range(1, N + 1):
		if dist_list[i] % 2 == 1:
			answer_list[i] = num_3m0
			num_3m0 += 3
		elif num_3m1 <= N:
			answer_list[i] = num_3m1
			num_3m1 += 3
		elif num_3m2 <= N:
			answer_list[i] = num_3m2
			num_3m2 += 3
		else:
			answer_list[i] = num_3m0
			num_3m0 += 3
else:
	for i in range(1, N + 1):
		if dist_list[i] % 2 == 0:
			if num_3m1 <= N:
				answer_list[i] = num_3m1
				num_3m1 += 3
			else:
				answer_list[i] = num_3m0
				num_3m0 += 3
		elif num_3m2 <= N:
			answer_list[i] = num_3m2
			num_3m2 += 3
		else:
			answer_list[i] = num_3m0
			num_3m0 += 3
print(*answer_list[1:])


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
sys.setrecursionlimit(10 ** 7)
n = int(input())
G = [[] for i in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
ans = [0] * n
color = [[], []]

def coloring(node, pre, oddeven):
	color[oddeven % 2].append(node)
	for vi in G[node]:
		if vi != pre:
			coloring(vi, node, oddeven + 1)
	return
coloring(0, -1, 0)
A = n // 3 + int(bool(n % 3))
B = n // 3 + int(n % 3 == 2)
C = n // 3
a = b = 0
c = 1
if len(color[0]) > C and len(color[1]) > C:
	for (i, ci) in enumerate(color[0]):
		if i < A:
			ans[ci] = 3 * i + 1
		else:
			ans[ci] = 3 * c
			c += 1
	for (i, ci) in enumerate(color[1]):
		if i < B:
			ans[ci] = 3 * i + 2
		else:
			ans[ci] = 3 * c
			c += 1
elif len(color[0]) <= C:
	for (i, ci) in enumerate(color[0]):
		ans[ci] = 3 * c
		c += 1
	for (i, ci) in enumerate(color[1]):
		if a < A:
			ans[ci] = 3 * a + 1
			a += 1
		elif b < B:
			ans[ci] = 3 * b + 2
			b += 1
		else:
			ans[ci] = 3 * c
			c += 1
else:
	for (i, ci) in enumerate(color[1]):
		ans[ci] = 3 * c
		c += 1
	for (i, ci) in enumerate(color[0]):
		if a < A:
			ans[ci] = 3 * a + 1
			a += 1
		elif b < B:
			ans[ci] = 3 * b + 2
			b += 1
		else:
			ans[ci] = 3 * c
			c += 1
print(*ans)


import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
	if i % 3 == 0:
		two.append(i + 2)
	elif i % 3 == 1:
		three.append(i + 2)
	else:
		one.append(i + 2)
que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
	i = que.popleft()
	parity[dist[i] % 2] += 1
	for j in graph[i]:
		if dist[j] != -1:
			continue
		dist[j] = dist[i] + 1
		que.append(j)
if parity[0] <= n // 3 or parity[1] <= n // 3:
	rem = 0 if parity[0] < parity[1] else 1
	for (i, v) in enumerate(dist):
		if v % 2 == rem:
			num[i] = str(three.popleft())
		elif len(one) != 0:
			num[i] = str(one.popleft())
		elif len(two) != 0:
			num[i] = str(two.popleft())
		else:
			num[i] = str(three.popleft())
else:
	for (i, v) in enumerate(dist):
		if v % 2 == 0:
			if len(one) != 0:
				num[i] = str(one.popleft())
			elif len(three) != 0:
				num[i] = str(three.popleft())
			else:
				flag = False
				break
		elif len(two) != 0:
			num[i] = str(two.popleft())
		elif len(three) != 0:
			num[i] = str(three.popleft())
		else:
			flag = False
			break
print(' '.join(num))


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)
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())
		elif 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())
		elif numbers2:
			ansl.append(numbers2.pop())
		else:
			ansl.append(numbers3.pop())
	for a in ansl:
		print(a)


from collections import deque
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = info[i]
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
root = 0
visited = [-1] * n

def dfs(root):
	q = deque([root])
	visited[root] = 0
	while q:
		v = q.pop()
		for nxt_v in tree[v]:
			if visited[nxt_v] != -1:
				continue
			else:
				visited[nxt_v] = (visited[v] + 1) % 2
				q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
	if visited[i] == 0:
		cnt0 += 1
	else:
		cnt1 += 1
num1 = n // 3
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
	num1 += 1
if n % 3 >= 2:
	num2 += 1
ans = [0] * n
set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
	if i % 3 == 0:
		set3.add(i)
	elif i % 3 == 1:
		set1.add(i)
	elif i % 3 == 2:
		set2.add(i)
if cnt0 <= num3:
	for i in range(n):
		if visited[i] == 0:
			ans[i] = set3.pop()
		elif set1:
			ans[i] = set1.pop()
		elif set2:
			ans[i] = set2.pop()
		elif set3:
			ans[i] = set3.pop()
elif cnt1 <= num3:
	for i in range(n):
		if visited[i] == 1:
			ans[i] = set3.pop()
		elif set1:
			ans[i] = set1.pop()
		elif set2:
			ans[i] = set2.pop()
		elif set3:
			ans[i] = set3.pop()
else:
	num147 = 0
	num258 = 0
	num369 = 0
	for i in range(n):
		if visited[i] == 0:
			num = num147 * 3 + 1
			if num > n:
				num = num369 * 3 + 3
				ans[i] = num
				if num > n:
					error
					exit()
				set3.remove(num)
				num369 += 1
				continue
			ans[i] = num
			set1.remove(num)
			num147 += 1
		else:
			num = num258 * 3 + 2
			if num > n:
				num = num369 * 3 + 3
				if num > n:
					error
					exit()
				ans[i] = num
				set3.remove(num)
				num369 += 1
				continue
			ans[i] = num
			set2.remove(num)
			num258 += 1
	for i in range(n):
		if ans[i] == 0:
			if set1:
				ans[i] = set1.pop()
			elif set2:
				ans[i] = set2.pop()
			elif set3:
				ans[i] = set3.pop()
print(*ans)


N = int(input())
node = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	node[a - 1].append(b - 1)
	node[b - 1].append(a - 1)
group = [False] * N
parents = list(range(N))
stack = [0]
while stack:
	p = stack.pop()
	for c in node[p]:
		if c != parents[p]:
			parents[c] = p
			group[c] = not group[p]
			stack.append(c)
p = [0] * N
three = 3
if group.count(True) <= N // 3:
	other = 1
	for i in range(N):
		if not group[i] and other <= N:
			p[i] = other
			other += other % 3
		else:
			p[i] = three
			three += 3
elif group.count(False) <= N // 3:
	other = 1
	for i in range(N):
		if group[i] and other <= N:
			p[i] = other
			other += other % 3
		else:
			p[i] = three
			three += 3
else:
	(one, two) = (1, 2)
	for i in range(N):
		if not group[i] and one <= N:
			p[i] = one
			one += 3
		elif group[i] and two <= N:
			p[i] = two
			two += 3
		else:
			p[i] = three
			three += 3
print(' '.join(map(str, p)))


import sys
sys.setrecursionlimit(10 ** 7)

class Tree:
	(C, RL) = ({}, {})
	(R, N, D, S, P, T) = (None, None, None, None, None, None)
	TL = None

	def __init__(s, num):
		s.N = num

	def set(s, a, b):
		if a in s.C:
			s.C[a].append(b)
		else:
			s.C[a] = [b]
		if b in s.C:
			s.C[b].append(a)
		else:
			s.C[b] = [a]

	def makeRank(s, root):
		s.R = [0] * s.N
		s.R[root] = 1
		s.RL[1] = [root]
		s.S = {}
		s.P = [-1] * s.N
		F = [root]
		s.D = 2
		while F != []:
			Ft = []
			s.RL[s.D] = []
			for i in F:
				for j in s.C[i]:
					if s.R[j] == 0:
						s.R[j] = s.D
						Ft.append(j)
						s.RL[s.D].append(j)
						if i not in s.S:
							s.S[i] = [j]
						else:
							s.S[i].append(j)
						s.P[j] = i
			s.D += 1
			F = Ft

	def dfs(s, x, y, r):
		if x == y:
			return [x]
		for i in s.C[x]:
			if i != r:
				t = s.dfs(i, y, x)
				if t != False:
					return [x] + t
		return False

	def dist(s, x):
		t = [-1] * s.N
		S = [x]
		ans = x
		ansn = 0
		t[x] = 0
		while S != []:
			k = S.pop()
			for i in s.C[k]:
				if t[i] == -1:
					t[i] = t[k] + 1
					S.append(i)
					if t[i] > ansn:
						ansn = t[i]
						ans = i
		return (ans, ansn)

	def getDi(s, x=0):
		(a, _) = s.dfs(x)
		(b, ans) = s.dfs(a)
		return ans

	def getDeep(s, x):
		ans = 0
		if x in s.S:
			for i in s.S[x]:
				ans = max(ans, s.getDeep(i))
			return ans + 1
		else:
			return 0

	def getParent(s, x, n):
		if n == 0:
			return x
		if s.P[x] == -1:
			return -n
		return s.getParent(s.P[x], n - 1)

	def abList(s):
		A = []
		B = []
		for i in range(s.N):
			if s.R[i] % 2 == 0:
				A.append(i)
			else:
				B.append(i)
		if len(A) > len(B):
			return [B, A]
		else:
			return [A, B]
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
A = []
B = []
C = []
for i in range(1, N + 1):
	if i % 3 == 0:
		C.append(i)
	elif i % 3 == 1:
		A.append(i)
	else:
		B.append(i)
T = Tree(N)
for (a, b) in ab:
	a -= 1
	b -= 1
	T.set(a, b)
T.makeRank(0)
(A, B) = T.abList()
c = N // 3
Ans = [0] * N
if len(A) <= c:
	t = 3
	k = 1
	for i in A:
		Ans[i] = t
		t += 3
		c -= 1
	for i in range(N):
		if Ans[i] == 0:
			if c != 0:
				Ans[i] = t
				c -= 1
				t += 3
			else:
				Ans[i] = k
				k += 1
				if k % 3 == 0:
					k += 1
else:
	t = 3
	n = N // 3
	if N % 3 != 0:
		n += 1
	k = 1
	for i in range(n):
		Ans[A[i]] = k
		k += 3
	for i in range(n, len(A)):
		Ans[A[i]] = t
		t += 3
	n = N // 3
	if N % 3 == 2:
		n += 1
	k = 2
	for i in range(n):
		Ans[B[i]] = k
		k += 3
	for i in range(n, len(B)):
		Ans[B[i]] = t
		t += 3
print(' '.join(list(map(str, Ans))))


import sys
input = sys.stdin.readline
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n - 1)]
edges = {}
for i in range(1, n + 1):
	edges[i] = set()
for tmp in ab:
	(a, b) = tmp
	edges[a].add(b)
	edges[b].add(a)
group = [[], []]
g_flag = 0
next = {1}
while len(next) > 0:
	tmp = list(next)
	next = set()
	for i in tmp:
		group[g_flag].append(i)
		for j in edges[i]:
			next.add(j)
			edges[j].remove(i)
	g_flag = 1 - g_flag
even_n = len(group[0])
odd_n = len(group[1])
ans = [0] * (n + 1)
if (even_n > n // 3) & (odd_n > n // 3):
	g1 = group[0][:(n + 2) // 3]
	g2 = group[1][:(n + 1) // 3]
	g0 = group[0][(n + 2) // 3:] + group[1][(n + 1) // 3:]
elif even_n <= n // 3:
	g0 = group[0] + group[1][:n // 3 - even_n]
	g1 = group[1][n // 3 - even_n:n // 3 - even_n + (n + 2) // 3]
	g2 = group[1][n // 3 - even_n + (n + 2) // 3:]
else:
	g0 = group[1] + group[0][:n // 3 - odd_n]
	g1 = group[0][n // 3 - odd_n:n // 3 - odd_n + (n + 2) // 3]
	g2 = group[0][n // 3 - odd_n + (n + 2) // 3:]
for i in range((n + 2) // 3):
	ans[g1[i]] = i * 3 + 1
for i in range((n + 1) // 3):
	ans[g2[i]] = i * 3 + 2
for (i, val) in enumerate(g0):
	ans[val] = (i + 1) * 3
print(' '.join(map(str, ans[1:])))


def main():
	n = int(input())
	ab = [list(map(int, input().split())) for _ in [0] * (n - 1)]
	g = [[] for _ in [0] * n]
	[g[a - 1].append(b - 1) for (a, b) in ab]
	[g[b - 1].append(a - 1) for (a, b) in ab]
	root = 0
	d = [-1] * n
	d[root] = 0
	q = [root]
	cnt = 0
	while q:
		cnt += 1
		qq = []
		while q:
			i = q.pop()
			for j in g[i]:
				if d[j] == -1:
					d[j] = cnt
					qq.append(j)
		q = qq
	d = [i % 2 + 1 for i in d]
	d2 = [0] * n
	x = d.count(1)
	y = d.count(2)
	if x > n // 3 and y > n // 3:
		j1 = 1
		for i in range(n):
			if d[i] == 1:
				d2[i] = j1
				j1 += 3
				cnt += 1
		j2 = 2
		for i in range(n):
			if d[i] == 2:
				d2[i] = j2
				j2 += 3
		j3 = 3
		for i in range(n):
			if d2[i] > n:
				d2[i] = j3
				j3 += 3
	elif x <= n // 3:
		j3 = 3
		for i in range(n):
			if d[i] == 1:
				d2[i] = j3
				j3 += 3
		j2 = 1
		for i in range(n):
			if d[i] == 2:
				d2[i] = j2
				if j2 % 3 == 2:
					j2 += 2
				else:
					j2 += 1
		for i in range(n):
			if d2[i] > n:
				d2[i] = j3
				j3 += 3
	else:
		j3 = 3
		for i in range(n):
			if d[i] == 2:
				d2[i] = j3
				j3 += 3
		j2 = 1
		for i in range(n):
			if d[i] == 1:
				d2[i] = j2
				if j2 % 3 == 2:
					j2 += 2
				else:
					j2 += 1
		for i in range(n):
			if d2[i] > n:
				d2[i] = j3
				j3 += 3
	print(*d2)
main()


(n, *L) = map(int, open(0).read().split())
g = [[] for _ in range(n)]
for (a, b) in zip(*[iter(L)] * 2):
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
b = [-1] * n
b[0] = 0
q = [0]
while q:
	c = q.pop()
	for x in g[c]:
		if b[x] < 0:
			b[x] = 1 - b[c]
			q.append(x)
lab = [-1] * n
Z = [i for (i, x) in enumerate(b) if x == 0]
O = [i for (i, x) in enumerate(b) if x]
(z, o) = (len(Z), len(O))
if z <= n // 3 or o <= n // 3:
	(L, H) = (Z, O) if z <= n // 3 else (O, Z)
	(a, b) = (1, 3)
	for i in L:
		lab[i] = b
		b += 3
	for i in H:
		if b <= n:
			lab[i] = b
			b += 3
		else:
			lab[i] = a
			a += 1 if a % 3 == 1 else 2
else:
	(a, b, c) = (1, 2, 3)
	for i in Z:
		if a <= n:
			lab[i] = a
			a += 3
		else:
			lab[i] = c
			c += 3
	for i in O:
		if b <= n:
			lab[i] = b
			b += 3
		else:
			lab[i] = c
			c += 3
print(*lab)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
bp = [-1] * N
stack = [(0, None, 0)]
while stack:
	(v, p, b) = stack.pop()
	bp[v] = b
	b += 1
	b &= 1
	for u in graph[v]:
		if u == p:
			continue
		stack.append((u, v, b))
cnt0 = N // 3
cnt1 = (N + 2) // 3
cnt2 = (N + 1) // 3
vs0 = [i for (i, b) in enumerate(bp) if b == 0]
vs1 = [i for (i, b) in enumerate(bp) if b == 1]
ans_mod3 = [-1] * N
if bp.count(0) <= N // 3:
	for i in range(len(vs0)):
		ans_mod3[vs0.pop()] = 0
		cnt0 -= 1
elif bp.count(1) <= N // 3:
	for i in range(len(vs1)):
		ans_mod3[vs1.pop()] = 0
		cnt0 -= 1
else:
	for i in range(cnt1):
		ans_mod3[vs0.pop()] = 1
		cnt1 -= 1
	for i in range(cnt2):
		ans_mod3[vs1.pop()] = 2
		cnt2 -= 1
for _ in range(cnt0):
	if vs0:
		ans_mod3[vs0.pop()] = 0
	elif vs1:
		ans_mod3[vs1.pop()] = 0
for _ in range(cnt1):
	if vs0:
		ans_mod3[vs0.pop()] = 1
	elif vs1:
		ans_mod3[vs1.pop()] = 1
for _ in range(cnt2):
	if vs0:
		ans_mod3[vs0.pop()] = 2
	elif vs1:
		ans_mod3[vs1.pop()] = 2
st = [3, 1, 2]
ans = []
for a in ans_mod3:
	ans.append(st[a])
	st[a] += 3
print(*ans)


import sys
import math
mod = 10 ** 9 + 7
inf = float('inf')
from math import sqrt
from collections import deque
from collections import Counter
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
color = [-1 for i in range(n)]
color[0] = 0

def coloring(x):
	for i in G[x]:
		if color[i] != -1:
			continue
		color[i] = 1 - color[x]
		coloring(i)
coloring(0)
A = []
B = []
ans = [0 for i in range(n)]
for i in range(n):
	if color[i] == 0:
		A.append(i)
	else:
		B.append(i)
if 1:
	if len(A) > len(B):
		(A, B) = (B, A)
	if len(A) <= n // 3:
		qq = deque([i for i in range(3, n + 1, 3)] + [i for i in range(1, n + 1, 3)] + [i for i in range(2, n + 1, 3)])
		for i in A:
			ans[i] = qq.popleft()
		for i in B:
			ans[i] = qq.popleft()
		print(*ans)
		exit()
	else:
		qq = deque([i for i in range(1, n + 1, 3)] + [i for i in range(3, n + 1, 3)] + [i for i in range(2, n + 1, 3)])
		for i in A:
			ans[i] = qq.popleft()
		for i in B:
			ans[i] = qq.popleft()
		print(*ans)
		exit()


n = int(input())
ans = [0] * n
three = n // 3
two = (n - three) // 2
one = n - three - two
t = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	t[a].append(b)
	t[b].append(a)
th = []
Q = [0]
visited = {0}
ma = 0
thi = -1
while Q:
	th.append(Q)
	if len(Q) > ma:
		ma = len(Q)
		thi = len(th) - 1
	P = []
	for j in Q:
		for i in t[j]:
			if i not in visited:
				P.append(i)
				visited.add(i)
	Q = P
odd = even = 0
for i in range(len(th)):
	if i % 2 == 1:
		odd += len(th[i])
	else:
		even += len(th[i])
if odd > one + three:
	flag = 'error'
	d = 0
elif even > one + three:
	flag = 'error'
	d = 1
else:
	flag = 'normal'
if flag == 'error':
	sudenideta = set()
	num = 3
	for i in range(d, len(th), 2):
		for j in th[i]:
			ans[j] = num
			sudenideta.add(num)
			num += 3
	num = 1
	for i in range(d ^ 1, len(th), 2):
		for j in th[i]:
			while num in sudenideta:
				num += 1
			ans[j] = num
			sudenideta.add(num)
			num += 1
else:
	odd_num = 2
	even_num = 1
	three_num = 3
	for i in range(len(th)):
		for j in th[i]:
			if i % 2 == 1:
				if odd_num > n:
					ans[j] = three_num
					three_num += 3
				else:
					ans[j] = odd_num
					odd_num += 3
			elif even_num > n:
				ans[j] = three_num
				three_num += 3
			else:
				ans[j] = even_num
				even_num += 3
print(*ans)


import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline
(N, *ab) = map(int, read().split())
if N == 2:
	print(1, 2)
	exit()
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))
k2 = list(range(2, N + 1, 3))
start = ab[0]
color = 1
queue = deque([(start, color)])
colors = [0] * (N + 1)
colors[start] = 1
while queue:
	(V, c) = queue.popleft()
	c = -c
	for v in graph[V]:
		if colors[v] == 0:
			colors[v] = c
			queue.append((v, c))
black = colors.count(1)
white = N - black
three = (N - 3) // 3 + 1
if black <= three:
	b = k0[:black]
	w = k1 + k2 + k0[black:]
	answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
	print(' '.join(map(str, answer)))
elif white <= three:
	w = k0[:white]
	b = k1 + k2 + k0[white:]
	answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
	print(' '.join(map(str, answer)))
else:
	answer = [0] * (N + 1)
	for i in range(1, N + 1):
		if colors[i] == 1:
			if k1:
				answer[i] = k1.pop()
			else:
				answer[i] = k0.pop()
		elif k2:
			answer[i] = k2.pop()
		else:
			answer[i] = k0.pop()
	print(' '.join(map(str, answer[1:])))


N = int(input())
AB = [list(map(int, input().split())) for _ in [0] * (N - 1)]

def dist_bfs(N, E, start):
	d = [-1] * N
	d[start] = 0
	q = [start]
	while q:
		qq = []
		for i in q:
			di = d[i]
			for j in E[i]:
				if d[j] != -1:
					continue
				d[j] = di + 1
				q.append(j)
		q = qq
	return d
E = [[] for _ in [0] * N]
for (a, b) in AB:
	a -= 1
	b -= 1
	E[a].append(b)
	E[b].append(a)
D = dist_bfs(N, E, 0)
e = []
o = []
cnt = 0
for (i, d) in enumerate(D):
	if d % 2 == 0:
		e.append(i)
		cnt += 1
	else:
		o.append(i)
if cnt > N - cnt:
	(e, o) = (o, e)
	cnt = N - cnt
ans = [0] * N
if cnt <= N // 3:
	done = set()
	j = 3
	for i in e:
		ans[i] = j
		done.add(j)
		j += 3
	j = 1
	for i in o:
		ans[i] = j
		j += 1
		while j in done:
			j += 1
else:
	done = set()
	j = 1
	for i in e:
		ans[i] = j
		done.add(j)
		j += 3
		if j > N:
			j = 3
	j = 2
	for i in o:
		ans[i] = j
		j += 1
		while j in done:
			j += 1
print(*ans)


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))

def resolve():
	N = ir()
	edges = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = lr()
		edges[a - 1].append(b - 1)
		edges[b - 1].append(a - 1)
	one = N // 3 + min(1, N % 3)
	two = N // 3 + N % 3 // 2
	thr = N // 3
	ans = [0] * N
	ball = [0] * N
	cnt = 0
	dist = [-1] * N
	s = [0]
	dist[0] = 0
	while len(s) > 0:
		v = s.pop()
		for j in edges[v]:
			if dist[j] == -1:
				dist[j] = dist[v] + 1
				if dist[j] % 2 == 1:
					ball[j] = 1
					cnt += 1
				s.append(j)
	if cnt > N / 3 and N - cnt > N / 3:
		for i in range(N):
			if ball[i] == 1:
				ans[i] = 3 * one - 2
				one -= 1
			else:
				ans[i] = 3 * two - 1
				two -= 1
		for i in range(N):
			if ans[i] <= 0:
				ans[i] = 3 * thr
				thr -= 1
	elif cnt <= N / 3:
		for i in range(N):
			if ball[i] == 1:
				ans[i] = 3 * thr
				thr -= 1
		for i in range(N):
			if ans[i] <= 0:
				if thr > 0:
					ans[i] = 3 * thr
					thr -= 1
				elif two > 0:
					ans[i] = 3 * two - 1
					two -= 1
				else:
					ans[i] = 3 * one - 2
					one -= 1
	else:
		for i in range(N):
			if ball[i] == 0:
				ans[i] = 3 * thr
				thr -= 1
		for i in range(N):
			if ans[i] <= 0:
				if thr > 0:
					ans[i] = 3 * thr
					thr -= 1
				elif two > 0:
					ans[i] = 3 * two - 1
					two -= 1
				else:
					ans[i] = 3 * one - 2
					one -= 1
	print(*ans, sep=' ')
resolve()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))
import queue

def main():
	N = I()
	adj = [[] for _ in range(N)]
	mod1 = range(1, N + 1, 3)
	n1 = 0
	mod2 = range(2, N + 1, 3)
	n2 = 0
	mod12 = list(mod1) + list(mod2)
	n12 = 0
	mod3 = range(3, N + 1, 3)
	n3 = 0
	p = [0] * N
	for i in range(N - 1):
		(a, b) = MI()
		a -= 1
		b -= 1
		adj[a].append(b)
		adj[b].append(a)
	q = queue.Queue()
	q.put((0, -1, 0))
	d = [0] * N
	while not q.empty():
		(v, par, depth) = q.get()
		d[v] = depth % 2
		for i in range(len(adj[v])):
			nxt = adj[v][i]
			if nxt != par:
				q.put((nxt, v, depth + 1))
	dmod = [0, 0]
	for i in range(N):
		dmod[d[i]] += 1
	if dmod[0] <= N // 3:
		for i in range(N):
			if d[i] == 0:
				p[i] = mod3[n3]
				n3 += 1
			elif n12 < len(mod12):
				p[i] = mod12[n12]
				n12 += 1
			else:
				p[i] = mod3[n3]
				n3 += 1
	elif dmod[1] <= N // 3:
		for i in range(N):
			if d[i] == 1:
				p[i] = mod3[n3]
				n3 += 1
			elif n12 < len(mod12):
				p[i] = mod12[n12]
				n12 += 1
			else:
				p[i] = mod3[n3]
				n3 += 1
	else:
		for i in range(N):
			if d[i] == 1:
				if n1 < len(mod1):
					p[i] = mod1[n1]
					n1 += 1
				else:
					p[i] = mod3[n3]
					n3 += 1
			elif n2 < len(mod2):
				p[i] = mod2[n2]
				n2 += 1
			else:
				p[i] = mod3[n3]
				n3 += 1
	print(' '.join(map(str, p)))
main()


n = int(input())
dist = [-1] * n
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
from collections import deque
queue = deque([[0, i] for i in G[0]])
dist[0] = 0
while queue:
	(now, to) = queue.pop()
	if dist[to] != -1:
		continue
	dist[to] = 1 - dist[now]
	for i in G[to]:
		queue.appendleft([to, i])
q = sum(dist)
LAST = [0] * n
if n / 3 <= q and n / 3 <= n - q:
	A = [i for i in range(1, n + 1, 3)] + [0] * n
	B = [i for i in range(2, n + 1, 3)] + [0] * n
	now1 = 0
	now2 = 0
	for i in range(n):
		if dist[i]:
			LAST[i] = B[now2]
			now2 += 1
		else:
			LAST[i] = A[now1]
			now1 += 1
	w = 3
	for i in range(n):
		if LAST[i] == 0:
			LAST[i] = w
			w += 3
	print(*LAST)
elif n / 3 > q:
	w = 3
	for i in range(n):
		if dist[i]:
			LAST[i] = w
			w += 3
	A = [i for i in range(w, n + 1, 3)] + [i for i in range(1, n + 1) if i % 3 != 0]
	now = 0
	for i in range(n):
		if LAST[i] == 0:
			LAST[i] = A[now]
			now += 1
	print(*LAST)
else:
	w = 3
	for i in range(n):
		if dist[i] == 0:
			LAST[i] = w
			w += 3
	A = [i for i in range(w, n + 1, 3)] + [i for i in range(1, n + 1) if i % 3 != 0]
	now = 0
	for i in range(n):
		if LAST[i] == 0:
			LAST[i] = A[now]
			now += 1
	print(*LAST)


n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
seen = [0 for _ in range(n)]
clr = [2 for _ in range(n)]
seen[0] = 1
clr[0] = 0
now = [0]
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if seen[y] == 0:
				seen[y] = 1
				now.append(y)
				clr[y] = 1 - clr[x]
a = n - sum(clr)
b = sum(clr)
z1 = 1
z2 = 2
z3 = 3
g1 = (n + 2) // 3
g2 = (n + 1) // 3
g3 = n // 3
ans = [0 for _ in range(n)]
if a > g3 and b > g3:
	for i in range(n):
		if clr[i] == 0:
			if g1:
				ans[i] = z1
				z1 += 3
				g1 -= 1
			else:
				ans[i] = z3
				z3 += 3
		elif g2:
			ans[i] = z2
			z2 += 3
			g2 -= 1
		else:
			ans[i] = z3
			z3 += 3
elif a <= g3:
	g3 -= a
	for i in range(n):
		if clr[i] == 0:
			ans[i] = z3
			z3 += 3
		elif g3:
			ans[i] = z3
			z3 += 3
			g3 -= 1
		elif g1:
			ans[i] = z1
			z1 += 3
			g1 -= 1
		else:
			ans[i] = z2
			z2 += 3
elif b <= g3:
	g3 -= b
	for i in range(n):
		if clr[i] == 1:
			ans[i] = z3
			z3 += 3
		elif g3:
			ans[i] = z3
			z3 += 3
			g3 -= 1
		elif g1:
			ans[i] = z1
			z1 += 3
			g1 -= 1
		else:
			ans[i] = z2
			z2 += 3
else:
	err
print(' '.join(map(str, ans)))


def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	adj = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	from collections import deque
	que = deque()
	que.append(1)
	seen = [-1] * (N + 1)
	seen[1] = 0
	par = [0] * (N + 1)
	child = [[] for _ in range(N + 1)]
	seq = []
	one_num = 0
	while que:
		v = que.popleft()
		seq.append(v)
		for u in adj[v]:
			if seen[u] == -1:
				seen[u] = seen[v] ^ 1
				if seen[u]:
					one_num += 1
				par[u] = v
				child[v].append(u)
				que.append(u)
	seq.reverse()
	two_num = N - one_num
	one = list(range(1, N + 1, 3))
	two = list(range(2, N + 1, 3))
	three = list(range(3, N + 1, 3))
	three_num = N // 3
	ans = [0] * (N + 1)
	if one_num <= three_num:
		for v in range(1, N + 1):
			if seen[v]:
				ans[v] = three.pop()
			elif one:
				ans[v] = one.pop()
			elif two:
				ans[v] = two.pop()
			else:
				ans[v] = three.pop()
	elif two_num <= three_num:
		for v in range(1, N + 1):
			if not seen[v]:
				ans[v] = three.pop()
			elif one:
				ans[v] = one.pop()
			elif two:
				ans[v] = two.pop()
			else:
				ans[v] = three.pop()
	else:
		for v in range(1, N + 1):
			if seen[v]:
				if one:
					ans[v] = one.pop()
				else:
					ans[v] = three.pop()
			elif two:
				ans[v] = two.pop()
			else:
				ans[v] = three.pop()
	print(*ans[1:])
main()


import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
stack = [(1, 1)]
color = [0] * (n + 1)
while stack:
	(x, c) = stack.pop()
	color[x] = c
	for y in graph[x]:
		if color[y] == 0:
			stack.append((y, 3 - c))
ans = [0] * (n + 1)
cnt1 = 1
cnt2 = 2
cnt3 = 3
if color.count(1) >= (n * 2 + 2) // 3:
	for i in range(1, n + 1):
		if color[i] == 1:
			if cnt1 <= n:
				ans[i] = cnt1
				if cnt1 % 3 == 1:
					cnt1 += 1
				else:
					cnt1 += 2
			else:
				ans[i] = cnt3
				cnt3 += 3
		else:
			ans[i] = cnt3
			cnt3 += 3
elif color.count(2) >= (n * 2 + 2) // 3:
	for i in range(1, n + 1):
		if color[i] == 2:
			if cnt1 <= n:
				ans[i] = cnt1
				if cnt1 % 3 == 1:
					cnt1 += 1
				else:
					cnt1 += 2
			else:
				ans[i] = cnt3
				cnt3 += 3
		else:
			ans[i] = cnt3
			cnt3 += 3
else:
	c1 = []
	c2 = []
	for i in range(1, n + 1):
		if color[i] == 1:
			c1.append(i)
		else:
			c2.append(i)
	for x in c1:
		if cnt1 <= n:
			ans[x] = cnt1
			cnt1 += 3
		else:
			ans[x] = cnt3
			cnt3 += 3
	for x in c2:
		if cnt2 <= n:
			ans[x] = cnt2
			cnt2 += 3
		else:
			ans[x] = cnt3
			cnt3 += 3
ans = ans[1:]
print(*ans)


from collections import Counter

def main():
	N = int(input())
	AB = [list(map(int, input().split())) for _ in range(N - 1)]
	G = [[] for _ in range(N)]
	cnt = [0] * N
	for (a, b) in AB:
		G[a - 1].append(b - 1)
		G[b - 1].append(a - 1)
		cnt[a - 1] += 1
		cnt[b - 1] += 1
	CI = sorted(((c, i) for (i, c) in enumerate(cnt)), reverse=True)
	ans = [0] * N
	C = [0] * N
	stack = [(0, -1, 0)]
	while stack:
		(u, p, d) = stack.pop()
		for v in G[u]:
			if v != p:
				stack.append((v, u, d ^ 1))
				C[v] = d ^ 1
	X = sum(C)
	if X <= N // 3:
		D = [[i for i in range(1, N + 1, 3)] + [i for i in range(2, N + 1, 3)], [i for i in range(3, N + 1, 3)]]
		for i in range(N):
			if D[C[i]]:
				ans[i] = D[C[i]].pop()
			else:
				ans[i] = D[C[i] ^ 1].pop()
	elif N - X <= N // 3:
		D = [[i for i in range(3, N + 1, 3)], [i for i in range(1, N + 1, 3)] + [i for i in range(2, N + 1, 3)]]
		for i in range(N):
			if D[C[i]]:
				ans[i] = D[C[i]].pop()
			else:
				ans[i] = D[C[i] ^ 1].pop()
	else:
		D = [[i for i in range(1, N + 1, 3)], [i for i in range(2, N + 1, 3)], [i for i in range(3, N + 1, 3)]]
		for i in range(N):
			if D[C[i]]:
				ans[i] = D[C[i]].pop()
			else:
				ans[i] = D[2].pop()
	print(*ans)
main()


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
if N == 2:
	print(1, 2)
	exit()
es = [[] for i in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	es[b].append(a)
depth = [-1] * N
depth[0] = 0

def dfs(v, p=-1):
	for to in es[v]:
		if to == p:
			continue
		depth[to] = depth[v] + 1
		dfs(to, v)
dfs(0)
g1 = []
g2 = []
for (i, d) in enumerate(depth):
	if d % 2:
		g2.append(i)
	else:
		g1.append(i)
if len(g1) < len(g2):
	(g1, g2) = (g2, g1)
ans = [None] * N
if len(g2) <= N // 3:
	for n in range(1, N + 1):
		if n % 3 == 0:
			if g2:
				i = g2.pop()
			else:
				i = g1.pop()
		else:
			i = g1.pop()
		ans[i] = n
else:
	for n in range(1, N + 1, 3):
		i = g1.pop()
		ans[i] = n
	for n in range(2, N + 1, 3):
		i = g2.pop()
		ans[i] = n
	for n in range(3, N + 1, 3):
		if g1:
			i = g1.pop()
		else:
			i = g2.pop()
		ans[i] = n
print(*ans)


from collections import deque
(N, *L) = map(int, open(0).read().split())
E = [[] for i in range(N + 1)]
for (a, b) in zip(*[iter(L)] * 2):
	E[a].append(b)
	E[b].append(a)
q = deque([1])
dist = [-1] * (N + 1)
dist[1] = 0
dic = [[1], []]
while q:
	u = q.popleft()
	for v in E[u]:
		if dist[v] == -1:
			dist[v] = dist[u] + 1
			q.append(v)
			dic[dist[v] % 2].append(v)
a = len(dic[0])
b = len(dic[1])
seq = set(range(1, N + 1))
ver = set(range(1, N + 1))
ans = [0] * (N + 1)
if a > N // 3 and b > N // 3:
	for i in range(1, N + 1, 3):
		v = dic[1].pop()
		ans[v] = i
	q = 0
	for i in range(2, N + 1, 3):
		v = dic[0].pop()
		ans[v] = i
	m = 3
	while dic[0]:
		v = dic[0].pop()
		ans[v] = m
		m += 3
	while dic[1]:
		v = dic[1].pop()
		ans[v] = m
		m += 3
elif a <= N // 3:
	seq = set(range(1, N + 1))
	m = 3
	while dic[0]:
		v = dic[0].pop()
		ans[v] = m
		seq.remove(m)
		m += 3
	seq = list(seq)
	while dic[1]:
		v = dic[1].pop()
		ans[v] = seq.pop()
else:
	seq = set(range(1, N + 1))
	m = 3
	while dic[1]:
		v = dic[1].pop()
		ans[v] = m
		seq.remove(m)
		m += 3
	seq = list(seq)
	while dic[0]:
		v = dic[0].pop()
		ans[v] = seq.pop()
print(*ans[1:])


class Tree:

	def __init__(self, N):
		self.N = N
		self.D = (self.N - 1).bit_length()
		self.E = [{} for _ in range(N)]

	def add_edge(self, init, end, weight, undirected=False):
		self.E[init][end] = weight
		if undirected:
			self.E[end][init] = weight

	def lca_initialize(self):
		self.dfs(0)
		self.doubling()

	def dfs(self, root):
		self.parent = [None] * self.N
		self.depth = [None] * self.N
		self.dist = [float('inf')] * self.N
		self.parent[root] = -1
		self.depth[root] = 0
		self.dist[root] = 0
		stack = [root]
		while stack:
			v = stack.pop()
			for (u, d) in self.E[v].items():
				if self.depth[u] is not None:
					continue
				self.parent[u] = v
				self.depth[u] = self.depth[v] + 1
				self.dist[u] = self.dist[v] + d
				stack.append(u)

	def doubling(self):
		self.next = [[-1] * self.N for _ in range(self.D)]
		for v in range(self.N):
			self.next[0][v] = self.parent[v]
		for d in range(self.D - 1):
			for v in range(self.N):
				if self.next[d][v] != -1:
					self.next[d + 1][v] = self.next[d][self.next[d][v]]

	def lca(self, u, v):
		if self.depth[u] > self.depth[v]:
			(u, v) = (v, u)
		diff = self.depth[v] - self.depth[u]
		for i in range(diff.bit_length()):
			if diff & 1 << i:
				v = self.next[i][v]
		if u == v:
			return u
		for i in range(self.depth[u].bit_length() - 1, -1, -1):
			(pu, pv) = (self.next[i][u], self.next[i][v])
			if pu != pv:
				(u, v) = (pu, pv)
		return self.next[0][u]
N = int(input())
tr = Tree(N)
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	tr.add_edge(a - 1, b - 1, 1, undirected=True)
tr.dfs(0)
(d_odd, d_even) = ([], [])
rem = [[] for _ in range(3)]
for i in range(N):
	if tr.depth[i] % 2 == 0:
		d_even.append(i)
	else:
		d_odd.append(i)
	rem[(i + 1) % 3].append(i + 1)
P = [0] * N
if len(d_odd) < len(d_even):
	if len(d_odd) <= len(rem[0]):
		for i in d_odd:
			P[i] = rem[0].pop()
	else:
		for i in d_odd:
			if rem[2]:
				P[i] = rem[2].pop()
			else:
				P[i] = rem[0].pop()
	temp = rem[2] + rem[0] + rem[1]
	for i in d_even:
		P[i] = temp.pop()
else:
	if len(d_even) <= len(rem[0]):
		for i in d_even:
			P[i] = rem[0].pop()
	else:
		for i in d_even:
			if rem[2]:
				P[i] = rem[2].pop()
			else:
				P[i] = rem[0].pop()
	temp = rem[2] + rem[0] + rem[1]
	for i in d_odd:
		P[i] = temp.pop()
print(*P)


from collections import deque
import random
isdebug = 0
if isdebug == 0:
	N = int(input())
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		G[a - 1].append(b - 1)
		G[b - 1].append(a - 1)
else:
	N = 20 * 10 ** 4
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(a, b) = (random.randrange(i + 1), i + 1)
		G[a].append(b)
		G[b].append(a)
dist = [-1 for i in range(N)]
X = []
Y = []
q = deque([0])
dist[0] = 0
while len(q) > 0:
	r = q.popleft()
	if dist[r] % 2 == 0:
		X.append(r)
	else:
		Y.append(r)
	for p in G[r]:
		if dist[p] == -1:
			dist[p] = dist[r] + 1
			q.append(p)
P = [0 for i in range(N)]
que = deque([])
if min(len(X), len(Y)) <= N // 3:
	for i in range(1, N + 1):
		if i % 3 == 0:
			que.appendleft(i)
		else:
			que.append(i)
	if len(X) < len(Y):
		for i in X:
			t = que.popleft()
			P[i] = t
		for i in Y:
			t = que.pop()
			P[i] = t
	else:
		for i in Y:
			t = que.popleft()
			P[i] = t
		for i in X:
			t = que.pop()
			P[i] = t
else:
	for i in range(1, N + 1):
		if i % 3 == 0:
			que.appendleft(i)
	for i in range(1, N + 1):
		if i % 3 == 1:
			que.appendleft(i)
		elif i % 3 == 2:
			que.append(i)
	for i in X:
		t = que.popleft()
		P[i] = t
	for i in Y:
		t = que.pop()
		P[i] = t
print(*P)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
depth = [0] * N

def dfs(v, pv):
	for nv in edge[v]:
		if nv != pv:
			depth[nv] = depth[v] + 1
			dfs(nv, v)
dfs(0, -1)
even = 0
odd = 0
for i in range(N):
	if depth[i] % 2 == 0:
		even += 1
	else:
		odd += 1
ans = [0 for i in range(N)]
if N % 3 == 0:
	if min(even, odd) >= N // 3:
		evencount = 0
		oddcount = 0
		allcount = 0
		for i in range(N):
			if depth[i] % 2 == 0:
				if N // 3 > evencount:
					ans[i] = evencount * 3 + 1
					evencount += 1
				else:
					ans[i] = (allcount + 1) * 3
					allcount += 1
			elif N // 3 > oddcount:
				ans[i] = oddcount * 3 + 2
				oddcount += 1
			else:
				ans[i] = (allcount + 1) * 3
				allcount += 1
		print(*ans)
	elif N // 3 > even:
		allcount = 0
		d = 1
		for i in range(N):
			if depth[i] % 2 == 0:
				ans[i] = 3 * allcount + 3
				allcount += 1
		for i in range(N):
			if depth[i] % 2 == 1:
				if N // 3 > allcount:
					ans[i] = 3 * allcount + 3
					allcount += 1
				else:
					ans[i] = d
					if d % 3 == 1:
						d += 1
					else:
						d += 2
		print(*ans)
	else:
		allcount = 0
		d = 1
		for i in range(N):
			if depth[i] % 2 == 1:
				ans[i] = 3 * allcount + 3
				allcount += 1
		for i in range(N):
			if depth[i] % 2 == 0:
				if N // 3 > allcount:
					ans[i] = 3 * allcount + 3
					allcount += 1
				else:
					ans[i] = d
					if d % 3 == 1:
						d += 1
					else:
						d += 2
		print(*ans)
elif N % 3 == 2:
	if min(even, odd) >= N // 3 + 1:
		evencount = 0
		oddcount = 0
		allcount = 0
		for i in range(N):
			if depth[i] % 2 == 0:
				if N // 3 + 1 > evencount:
					ans[i] = evencount * 3 + 1
					evencount += 1
				else:
					ans[i] = (allcount + 1) * 3
					allcount += 1
			elif N // 3 + 1 > oddcount:
				ans[i] = oddcount * 3 + 2
				oddcount += 1
			else:
				ans[i] = (allcount + 1) * 3
				allcount += 1
		print(*ans)
	elif N // 3 + 1 > even:
		allcount = 0
		d = 1
		for i in range(N):
			if depth[i] % 2 == 0:
				ans[i] = 3 * allcount + 3
				allcount += 1
		for i in range(N):
			if depth[i] % 2 == 1:
				if N // 3 > allcount:
					ans[i] = 3 * allcount + 3
					allcount += 1
				else:
					ans[i] = d
					if d % 3 == 1:
						d += 1
					else:
						d += 2
		print(*ans)
	else:
		allcount = 0
		d = 1
		for i in range(N):
			if depth[i] % 2 == 1:
				ans[i] = 3 * allcount + 3
				allcount += 1
		for i in range(N):
			if depth[i] % 2 == 0:
				if N // 3 > allcount:
					ans[i] = 3 * allcount + 3
					allcount += 1
				else:
					ans[i] = d
					if d % 3 == 1:
						d += 1
					else:
						d += 2
		print(*ans)
elif even >= N // 3 + 1 and odd >= N // 3:
	evencount = 0
	oddcount = 0
	allcount = 0
	for i in range(N):
		if depth[i] % 2 == 0:
			if N // 3 + 1 > evencount:
				ans[i] = evencount * 3 + 1
				evencount += 1
			else:
				ans[i] = (allcount + 1) * 3
				allcount += 1
		elif N // 3 > oddcount:
			ans[i] = oddcount * 3 + 2
			oddcount += 1
		else:
			ans[i] = (allcount + 1) * 3
			allcount += 1
	print(*ans)
elif even >= N // 3 and odd >= N // 3 + 1:
	evencount = 0
	oddcount = 0
	allcount = 0
	for i in range(N):
		if depth[i] % 2 == 1:
			if N // 3 + 1 > evencount:
				ans[i] = evencount * 3 + 1
				evencount += 1
			else:
				ans[i] = (allcount + 1) * 3
				allcount += 1
		elif N // 3 > oddcount:
			ans[i] = oddcount * 3 + 2
			oddcount += 1
		else:
			ans[i] = (allcount + 1) * 3
			allcount += 1
	print(*ans)
elif N // 3 >= even:
	allcount = 0
	d = 1
	for i in range(N):
		if depth[i] % 2 == 0:
			ans[i] = 3 * allcount + 3
			allcount += 1
	for i in range(N):
		if depth[i] % 2 == 1:
			if N // 3 > allcount:
				ans[i] = 3 * allcount + 3
				allcount += 1
			else:
				ans[i] = d
				if d % 3 == 1:
					d += 1
				else:
					d += 2
	print(*ans)
else:
	allcount = 0
	d = 1
	for i in range(N):
		if depth[i] % 2 == 1:
			ans[i] = 3 * allcount + 3
			allcount += 1
	for i in range(N):
		if depth[i] % 2 == 0:
			if N // 3 > allcount:
				ans[i] = 3 * allcount + 3
				allcount += 1
			else:
				ans[i] = d
				if d % 3 == 1:
					d += 1
				else:
					d += 2
	print(*ans)


from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a - 1, b - 1) for (a, b) in AB]
for (itr, (a, b)) in enumerate(AB):
	e[a].append(b)
	e[b].append(a)
colors = [-1] * n
q = deque()
q.append((0, 0))
while q:
	(v, pcol) = q.popleft()
	if colors[v] == -1:
		col = not pcol
		colors[v] = col
		for i in e[v]:
			if colors[i] == -1:
				q.append((i, col))
m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

def opop(n, ne):
	if m[n]:
		p = m[n].pop()
	elif n == 1 or n == 2:
		if m[ne]:
			p = m[ne].pop()
		else:
			p = m[0].pop()
	elif m[1]:
		p = m[1].pop()
	else:
		p = m[2].pop()
	return p
ans = [0] * n
if sum(colors) <= len(m[0]):
	for (itr, i) in enumerate(colors):
		if i:
			ans[itr] = opop(0, 0)
		else:
			ans[itr] = opop(1, 2)
elif sum(colors) >= len(m[1]) + len(m[2]):
	for (itr, i) in enumerate(colors):
		if not i:
			ans[itr] = opop(0, 0)
		else:
			ans[itr] = opop(1, 2)
else:
	for (itr, i) in enumerate(colors):
		if i:
			ans[itr] = opop(1, 0)
		else:
			ans[itr] = opop(2, 0)
print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
E = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
mod = [3, 1, 2]
ans = [0 for i in range(n)]
count = [0, 0]

def bfs(cur, pre, c):
	stack = deque([[cur, pre, c]])
	while stack:
		(cur, pre, c) = stack.popleft()
		count[c % 2] += 1
		for e in E[cur]:
			if e != pre:
				stack.append([e, cur, c + 1])

def case1(cur, pre, c, i):
	stack = deque([[cur, pre, c]])
	while stack:
		(cur, pre, c) = stack.popleft()
		t = c % 2
		if t == i:
			ans[cur] = mod[0]
			mod[0] += 3
		elif mod[1] <= n:
			ans[cur] = mod[1]
			mod[1] += 3
		elif mod[2] <= n:
			ans[cur] = mod[2]
			mod[2] += 3
		else:
			ans[cur] = mod[0]
			mod[0] += 3
		for e in E[cur]:
			if e != pre:
				stack.append([e, cur, c + 1])

def case2(cur, pre, c):
	stack = deque([[cur, pre, c]])
	while stack:
		(cur, pre, c) = stack.popleft()
		t = c % 2
		if mod[t + 1] <= n:
			ans[cur] = mod[t + 1]
			mod[t + 1] += 3
		else:
			ans[cur] = mod[0]
			mod[0] += 3
		for e in E[cur]:
			if e != pre:
				stack.append([e, cur, c + 1])
bfs(0, -1, 0)
if count[0] < (n + 2) // 3:
	case1(0, -1, 0, 0)
elif count[1] < (n + 2) // 3:
	case1(0, -1, 0, 1)
else:
	case2(0, -1, 0)
print(' '.join([str(i) for i in ans]))


import sys
input = sys.stdin.readline
n = int(input())
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
ans = [-1] * (n + 1)
q = [1]
ans[1] = 0
while q:
	now = q.pop()
	for next in tree[now]:
		if ans[next] == -1:
			q.append(next)
			ans[next] = (ans[now] + 1) % 2
if ans.count(1) <= n // 3:
	three = set([3 * i + 3 for i in range(n // 3)])
	onetwo = set([i + 1 for i in range(n)])
	onetwo = onetwo - three
	three = list(three)
	three.sort()
	onetwo = list(onetwo)
	onetwo.sort()
	three_ind = 0
	onetwo_ind = 0
	for i in range(1, n + 1):
		if ans[i] == 1:
			ans[i] = three[three_ind]
			three_ind += 1
		elif onetwo_ind >= len(onetwo):
			ans[i] = three[three_ind]
			three_ind += 1
		else:
			ans[i] = onetwo[onetwo_ind]
			onetwo_ind += 1
elif ans.count(0) <= n // 3:
	three = set([3 * i + 3 for i in range(n // 3)])
	onetwo = set([i + 1 for i in range(n)])
	onetwo = onetwo - three
	three = list(three)
	three.sort()
	onetwo = list(onetwo)
	onetwo.sort()
	three_ind = 0
	onetwo_ind = 0
	for i in range(1, n + 1):
		if ans[i] == 0:
			ans[i] = three[three_ind]
			three_ind += 1
		elif onetwo_ind >= len(onetwo):
			ans[i] = three[three_ind]
			three_ind += 1
		else:
			ans[i] = onetwo[onetwo_ind]
			onetwo_ind += 1
else:
	zero = 0
	one = 0
	two = 0
	for i in range(1, n + 1):
		if ans[i] == 0:
			ans[i] = zero * 3 + 1
			zero += 1
		elif ans[i] == 1:
			ans[i] = one * 3 + 2
			one += 1
	three = 0
	for i in range(1, n + 1):
		if ans[i] > n:
			ans[i] = three * 3 + 3
			three += 1
print(' '.join(map(str, ans[1:])))


import sys, bisect, math, itertools, string, queue, copy
from collections import Counter, defaultdict, deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inpm():
	return map(int, input().split())

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

def inpls():
	return list(input().split())

def inplm(n):
	return list((int(input()) for _ in range(n)))

def inplL(n):
	return [list(input()) for _ in range(n)]

def inplT(n):
	return [tuple(input()) for _ in range(n)]

def inpll(n):
	return [list(map(int, input().split())) for _ in range(n)]

def inplls(n):
	return sorted([list(map(int, input().split())) for _ in range(n)])

def bfs(n, g):
	dis = [-1 for _ in range(n)]
	que = deque([])
	que.append(0)
	dis[0] = 0
	ODD = []
	EVEN = [0]
	while que:
		go = que.pop()
		for i in range(len(g[go])):
			if dis[g[go][i]] != -1:
				continue
			dis[g[go][i]] = dis[go] + 1
			if dis[g[go][i]] % 2 == 0:
				EVEN.append(g[go][i])
			else:
				ODD.append(g[go][i])
			que.append(g[go][i])
	return (EVEN, ODD)

def main():
	n = inp()
	g = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = inpm()
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	(EVEN, ODD) = bfs(n, g)
	ans = [0 for _ in range(n)]
	check = [1 for _ in range(n)]
	mod0 = deque()
	mod1 = deque()
	mod2 = deque()
	for i in range(1, n + 1):
		if i % 3 == 0:
			mod0.append(i)
		if i % 3 == 1:
			mod1.append(i)
		if i % 3 == 2:
			mod2.append(i)
	if len(ODD) <= n // 3:
		x = 1
		while ODD:
			index = ODD.pop()
			ans[index] = 3 * x
			check[3 * x - 1] = 0
			x += 1
		i = 0
		while EVEN:
			index = EVEN.pop()
			while not check[i]:
				i += 1
			ans[index] = i + 1
			i += 1
		print(*ans)
		return
	if len(EVEN) <= n // 3:
		x = 1
		while EVEN:
			index = EVEN.pop()
			ans[index] = 3 * x
			check[3 * x - 1] = 0
			x += 1
		i = 0
		while ODD:
			index = ODD.pop()
			while not check[i]:
				i += 1
			ans[index] = i + 1
			i += 1
		print(*ans)
		return
	if len(ODD) <= len(EVEN):
		while mod1:
			index = EVEN.pop()
			ans[index] = mod1.pop()
		while mod2:
			index = ODD.pop()
			ans[index] = mod2.pop()
	else:
		while mod1:
			index = ODD.pop()
			ans[index] = mod1.pop()
		while mod2:
			index = EVEN.pop()
			ans[index] = mod2.pop()
	while mod0:
		if EVEN:
			index = EVEN.pop()
		else:
			index = ODD.pop()
		ans[index] = mod0.pop()
	print(*ans)
main()


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	T[a].append(b)
	T[b].append(a)
L = [-1] * n
dist = [-1] * n
dist[0] = 0
F_1 = [i for i in range(1, n + 1) if i % 3 == 1]
F_2 = [i for i in range(1, n + 1) if i % 3 == 2]
F_0 = [i for i in range(1, n + 1) if i % 3 == 0]

def dfs(v):
	for nv in T[v]:
		if dist[nv] == -1:
			dist[nv] = dist[v] ^ 1
			dfs(nv)
dfs(0)
l0 = dist.count(0)
l1 = n - l0
if l0 <= n // 3:
	for i in range(n):
		if dist[i] == 0:
			L[i] = F_0.pop()
		elif F_1:
			L[i] = F_1.pop()
		elif F_2:
			L[i] = F_2.pop()
		else:
			L[i] = F_0.pop()
elif l1 <= n // 3:
	for i in range(n):
		if dist[i]:
			L[i] = F_0.pop()
		elif F_1:
			L[i] = F_1.pop()
		elif F_2:
			L[i] = F_2.pop()
		else:
			L[i] = F_0.pop()
else:
	for i in range(n):
		if dist[i]:
			if F_1:
				L[i] = F_1.pop()
			else:
				L[i] = F_0.pop()
		elif F_2:
			L[i] = F_2.pop()
		else:
			L[i] = F_0.pop()
print(*L)


import sys
input = sys.stdin.readline
(N,) = map(int, input().split())
G = [set() for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].add(b)
	G[b].add(a)
xs = [[] for _ in range(2)]
g2 = [set() for _ in range(N + 1)]
vs = set()
stack = [1]
depth = [0] * (N + 1)
dfs_vs = []
vs.add(1)
while stack:
	v = stack.pop()
	xs[depth[v] % 2].append(v)
	dfs_vs.append(v)
	for u in G[v]:
		if u in vs:
			continue
		depth[u] = depth[v] + 1
		g2[v].add(u)
		stack.append(u)
		vs.add(u)
xs.sort(key=lambda x: len(x))
rs = []
if len(xs[0]) <= N // 3:
	i = j = k = 0
	for x in xs[0]:
		i += 1
		rs.append((x, 3 * i))
	for x in xs[1]:
		if i + 1 <= N // 3:
			i += 1
			rs.append((x, 3 * i))
		elif j <= (N - 1) // 3:
			rs.append((x, 3 * j + 1))
			j += 1
		else:
			rs.append((x, 3 * k + 2))
			k += 1
else:
	i = j = k = 0
	for x in xs[0]:
		if j <= (N - 1) // 3:
			rs.append((x, 3 * j + 1))
			j += 1
		elif i + 1 <= N // 3:
			i += 1
			rs.append((x, 3 * i))
	for x in xs[1]:
		if i + 1 <= N // 3:
			i += 1
			rs.append((x, 3 * i))
		else:
			rs.append((x, 3 * k + 2))
			k += 1
rs.sort(key=lambda x: x[0])
print(' '.join((str(x[1]) for x in rs)))


import sys
input = sys.stdin.readline
N = int(input())
P = [0 for i in range(N + 1)]
L = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	L[a].append(b)
	L[b].append(a)
d1 = [10 ** 9 for i in range(N + 1)]
d1[1] = 0
Q = []
for i in L[1]:
	Q.append([i, 1])
for i in range(N - 1):
	d1[Q[i][0]] = Q[i][1]
	for j in L[Q[i][0]]:
		if d1[j] == 10 ** 9:
			Q.append([j, Q[i][1] + 1])
ODD = 0
EVE = 0
for i in range(1, N + 1):
	if d1[i] % 2 == 0:
		EVE += 1
	else:
		ODD += 1
M1 = []
M2 = []
M3 = []
for i in range(1, N + 1):
	if i % 3 == 1:
		M1.append(i)
	elif i % 3 == 2:
		M2.append(i)
	else:
		M3.append(i)
if min(ODD, EVE) * 2 < max(ODD, EVE):
	if ODD < EVE:
		D = {}
		ans = [0 for i in range(N + 1)]
		cnt = 0
		for i in range(1, N + 1):
			if d1[i] % 2 == 1:
				ans[i] = M3[cnt]
				D[M3[cnt]] = 1
				cnt += 1
		num = 1
		for i in range(1, N + 1):
			if d1[i] % 2 == 0:
				if num in D:
					num += 1
				ans[i] = num
				num += 1
	else:
		D = {}
		ans = [0 for i in range(N + 1)]
		cnt = 0
		for i in range(1, N + 1):
			if d1[i] % 2 == 0:
				ans[i] = M3[cnt]
				D[M3[cnt]] = 1
				cnt += 1
		num = 1
		for i in range(1, N + 1):
			if d1[i] % 2 == 1:
				if num in D:
					num += 1
				ans[i] = num
				num += 1
	print(*ans[1:])
else:
	ans = [0 for i in range(N + 1)]
	m1 = 0
	m2 = 0
	m3 = 0
	for i in range(1, N + 1):
		if d1[i] % 2 == 0:
			if m1 < len(M1):
				ans[i] = M1[m1]
				m1 += 1
			else:
				ans[i] = M3[m3]
				m3 += 1
		elif m2 < len(M2):
			ans[i] = M2[m2]
			m2 += 1
		else:
			ans[i] = M3[m3]
			m3 += 1
	print(*ans[1:])


import sys
from collections import deque
input = sys.stdin.readline

def main():
	n = int(input())
	tree = [[] for _ in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		tree[a - 1].append(b - 1)
		tree[b - 1].append(a - 1)
	not_yet = deque([0])
	already = [False] * n
	already[0] = True
	dist = [0] * n
	while not_yet:
		value = not_yet.popleft()
		for v in tree[value]:
			if already[v]:
				continue
			already[v] = True
			dist[v] = (dist[value] + 1) % 2
			not_yet.append(v)
	zero = dist.count(0)
	one = dist.count(1)
	ans = [0] * n
	already = [False] * n
	if zero >= one:
		if one <= n // 3:
			ind = 1
			for i in range(n):
				if dist[i] == 1:
					ans[i] = ind * 3
					already[ind * 3 - 1] = True
					ind += 1
			ind = 0
			for i in range(n):
				if ans[i] == 0:
					while already[ind]:
						ind += 1
					ans[i] = ind + 1
					already[ind] = True
		else:
			(c0, c1, c2) = (0, 0, 1)
			(z, o) = (n // 3 + bool(n % 3), n // 3 + bool(n % 3 == 2))
			for i in range(n):
				if dist[i] == 0:
					if c0 >= z:
						ans[i] = c2 * 3
						c2 += 1
						continue
					ans[i] = c0 * 3 + 1
					c0 += 1
				else:
					if c1 >= o:
						ans[i] = c2 * 3
						c2 += 1
						continue
					ans[i] = c1 * 3 + 2
					c1 += 1
	elif zero <= n // 3:
		ind = 1
		for i in range(n):
			if dist[i] == 0:
				ans[i] = ind * 3
				already[ind * 3 - 1] = True
				ind += 1
		ind = 0
		for i in range(n):
			if ans[i] == 0:
				while already[ind]:
					ind += 1
				ans[i] = ind + 1
				already[ind] = True
	else:
		(c0, c1, c2) = (0, 0, 1)
		(z, o) = (n // 3 + bool(n % 3), n // 3 + bool(n % 3 == 2))
		for i in range(n):
			if dist[i] == 1:
				if c0 >= z:
					ans[i] = c2 * 3
					c2 += 1
					continue
				ans[i] = c0 * 3 + 1
				c0 += 1
			else:
				if c1 >= o:
					ans[i] = c2 * 3
					c2 += 1
					continue
				ans[i] = c1 * 3 + 2
				c1 += 1
	print(*ans)
main()


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
adjacent_list = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adjacent_list[a].append(b)
	adjacent_list[b].append(a)
finished = set()
inf = 10 ** 9
dist = [inf for i in range(n + 1)]

def dfs(node):
	finished.add(node)
	for i in adjacent_list[node]:
		if i not in finished:
			dist[i] = dist[node] + 1
			dfs(i)
dist[1] = 0
rem_1 = [i + 1 for i in range(n) if (i + 1) % 3 == 1]
rem_2 = [i + 1 for i in range(n) if (i + 1) % 3 == 2]
rem_0 = [i + 1 for i in range(n) if (i + 1) % 3 == 0]
index_0 = 0
index_1 = 0
index_2 = 0
dfs(1)
ans = []
count_even = 0
count_odd = 0
for i in range(1, len(dist)):
	if dist[i] % 2 == 0:
		count_even += 1
	else:
		count_odd += 1
if count_even > n / 3 and count_odd > n / 3:
	for i in range(1, len(dist)):
		if dist[i] % 2 == 1:
			if index_2 < len(rem_2):
				ans.append(rem_2[index_2])
				index_2 += 1
			else:
				ans.append(rem_0[index_0])
				index_0 += 1
		elif index_1 < len(rem_1):
			ans.append(rem_1[index_1])
			index_1 += 1
		else:
			ans.append(rem_0[index_0])
			index_0 += 1
elif count_even <= n / 3:
	li = rem_1 + rem_2
	index = 0
	for i in range(1, len(dist)):
		if dist[i] % 2 == 0:
			ans.append(rem_0[index_0])
			index_0 += 1
		elif index < len(li):
			ans.append(li[index])
			index += 1
		else:
			ans.append(rem_0[index_0])
			index_0 += 1
else:
	li = rem_1 + rem_2
	index = 0
	for i in range(1, len(dist)):
		if dist[i] % 2 == 1:
			ans.append(rem_0[index_0])
			index_0 += 1
		elif index < len(li):
			ans.append(li[index])
			index += 1
		else:
			ans.append(rem_0[index_0])
			index_0 += 1
for i in ans:
	print(i, end=' ')


import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
a = [1]
b = []
s = [1]
vis = [0] * (N + 1)
table = [-1] * (N + 1)
table[1] = 1
vis[1] = 1
while len(s):
	x = s.pop()
	for y in e[x]:
		if vis[y]:
			continue
		vis[y] = 1
		table[y] = table[x] ^ 1
		if table[y]:
			a.append(y)
		else:
			b.append(y)
		s.append(y)
if len(a) > len(b):
	(a, b) = (b, a)
res = [0] * (N + 1)
if len(a) <= N // 3:
	ss = set([x for x in range(1, N + 1)])
	x = 3
	for y in a:
		res[y] = x
		ss.discard(x)
		x += 3
	ss = list(ss)
	for i in range(1, N + 1):
		if res[i]:
			continue
		res[i] = ss.pop()
	print(*res[1:])
else:
	ss = set([x for x in range(1, N + 1)])
	x = 2
	for y in a:
		res[y] = x
		ss.discard(x)
		x += 3
		if x > N:
			break
	x = 3
	for y in a:
		if res[y]:
			continue
		res[y] = x
		ss.discard(x)
		x += 3
	ss = list(ss)
	for i in range(1, N + 1):
		if res[i]:
			continue
		res[i] = ss.pop()
	print(*res[1:])


import sys
n = int(input())
l = [list(map(int, input().split())) for i in range(n - 1)]
connection = [[] for i in range(n)]
for i in range(n - 1):
	connection[l[i][0] - 1].append(l[i][1] - 1)
	connection[l[i][1] - 1].append(l[i][0] - 1)

def bfs(v):
	distance = [-1] * n
	distance[v] = 0
	next = connection[v]
	next2 = set()
	visited = [-1] * n
	visited[v] = 1
	visitct = 1
	ct = 0
	while len(next) != 0 and visitct != n:
		ct += 1
		for i in range(len(next)):
			if visited[next[i]] == -1:
				distance[next[i]] = ct
				visited[next[i]] = 1
				visitct += 1
				for j in range(len(connection[next[i]])):
					if visited[connection[next[i]][j]] == -1:
						next2.add(connection[next[i]][j])
		next = list(next2)
		next2 = set()
	return distance
b = bfs(0)
ct0 = 0
ct1 = 0
for i in range(n):
	b[i] %= 2
	if b[i] == 0:
		ct0 += 1
	else:
		ct1 += 1
ans = [0] * n
x1 = 1
x2 = 2
x3 = 3
if ct0 >= n // 3 + 1 and ct1 >= n // 3 + 1:
	for i in range(n):
		if b[i] == 0:
			if x1 <= n:
				ans[i] = x1
				x1 += 3
			else:
				ans[i] = x3
				x3 += 3
		elif x2 <= n:
			ans[i] = x2
			x2 += 3
		else:
			ans[i] = x3
			x3 += 3
elif ct0 <= n // 3:
	for i in range(n):
		if b[i] == 0:
			ans[i] = x3
			x3 += 3
		elif x1 <= n:
			ans[i] = x1
			x1 += 3
		elif x2 <= n:
			ans[i] = x2
			x2 += 3
		else:
			ans[i] = x3
			x3 += 3
elif ct1 <= n // 3:
	for i in range(n):
		if b[i] == 1:
			ans[i] = x3
			x3 += 3
		elif x1 <= n:
			ans[i] = x1
			x1 += 3
		elif x2 <= n:
			ans[i] = x2
			x2 += 3
		else:
			ans[i] = x3
			x3 += 3
for i in range(n):
	ans[i] = str(ans[i])
print(' '.join(ans))


def solve(*args: str) -> str:
	n = int(args[0])
	T = {i: set() for i in range(1, n + 1)}
	for ab in map(str.split, args[1:]):
		(a, b) = map(int, ab)
		T[a].add(b)
		T[b].add(a)
	R = set()
	B = set()
	stack = [(1, 0)]
	while stack:
		(i, d) = stack.pop()
		if i in R or i in B:
			continue
		if d % 2:
			R.add(i)
		else:
			B.add(i)
		for j in T[i]:
			stack.append((j, d + 1))
	(R, B) = (R, B) if len(R) < len(B) else (B, R)
	ret = [0] * (n + 1)
	if len(R) <= n // 3:
		for i in range(1, n + 1):
			if i % 3:
				ret[B.pop()] = i
			else:
				ret[R.pop() if R else B.pop()] = i
	else:
		for i in range(1, n + 1, 3):
			ret[R.pop()] = i
		for i in range(2, n + 1, 3):
			ret[B.pop()] = i
		for i in range(3, n + 1, 3):
			ret[R.pop() if R else B.pop()] = i
	return ' '.join(map(str, ret[1:]))
print(solve(*open(0).read().splitlines()))


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
col = [-1] * N
col[0] = 0
stack = deque([0])
while stack:
	now = stack.pop()
	for i in G[now]:
		if col[i] == -1:
			col[i] = (col[now] + 1) % 2
			stack.append(i)
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]
ans = [0 for _ in range(N)]
if sum(col) <= N // 3:
	mods = deque(mod0 + mod1 + mod2)
	for i in range(N):
		if col[i] == 1:
			ans[i] = mods.popleft()
		else:
			ans[i] = mods.pop()
elif sum(col) >= 2 * N // 3:
	mods = deque(mod0 + mod1 + mod2)
	for i in range(N):
		if col[i] == 0:
			ans[i] = mods.popleft()
		else:
			ans[i] = mods.pop()
else:
	mods = deque(mod1 + mod0 + mod2)
	for i in range(N):
		if col[i] == 0:
			ans[i] = mods.popleft()
		else:
			ans[i] = mods.pop()
print(*ans)


n = int(input())
ki = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	ki[a].append(b)
	ki[b].append(a)
odd = [-1] * n
odd[0] = 0
todo = [0]
while todo:
	v = todo.pop()
	for nv in ki[v]:
		if odd[nv] == -1:
			odd[nv] = abs(odd[v] - 1)
			todo.append(nv)
from collections import Counter
co = Counter(odd)
ans = [0] * n
if co[1] <= n // 3:
	cnt1 = 1
	cnt2 = 0
	cnt3 = 1
	for i in range(n):
		if odd[i] == 1 and 3 * cnt3 <= n:
			ans[i] = 3 * cnt3
			cnt3 += 1
		else:
			if cnt1 % 3 == 0:
				cnt1 += 1
			if cnt1 <= n:
				ans[i] = cnt1
				cnt1 += 1
			else:
				ans[i] = n - n % 3 - cnt2 * 3
				cnt2 += 1
elif co[0] <= n // 3:
	cnt1 = 1
	cnt2 = 0
	cnt3 = 1
	for i in range(n):
		if odd[i] == 0 and 3 * cnt3 <= n:
			ans[i] = 3 * cnt3
			cnt3 += 1
		else:
			if cnt1 % 3 == 0:
				cnt1 += 1
			if cnt1 <= n:
				ans[i] = cnt1
				cnt1 += 1
			else:
				ans[i] = n - n % 3 - cnt2 * 3
				cnt2 += 1
else:
	cnt1 = 1
	cnt2 = 1
	cnt3 = 1
	for i in range(n):
		if odd[i] == 1:
			if 3 * cnt1 - 2 <= n:
				ans[i] = 3 * cnt1 - 2
				cnt1 += 1
			else:
				ans[i] = 3 * cnt3
				cnt3 += 1
		elif 3 * cnt2 - 1 <= n:
			ans[i] = 3 * cnt2 - 1
			cnt2 += 1
		else:
			ans[i] = 3 * cnt3
			cnt3 += 1
print(*ans, sep=' ')


import sys
input = sys.stdin.readline
from collections import *

def bfs():
	q = deque([0])
	color = [0] * N
	color[0] = 1
	while q:
		v = q.popleft()
		for nv in G[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
	return color
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
cnt = [0] * 3
for i in range(1, N + 1):
	cnt[i % 3] += 1
color = bfs()
m = color.count(1)
ans = [-1] * N
if m <= cnt[0]:
	(c0, c1, c2) = (3, 1, 2)
	for i in range(N):
		if color[i] == 1:
			ans[i] = c0
			c0 += 3
	for i in range(N):
		if color[i] == -1:
			if c0 <= N:
				ans[i] = c0
				c0 += 3
			elif c1 <= N:
				ans[i] = c1
				c1 += 3
			else:
				ans[i] = c2
				c2 += 3
elif m >= N - cnt[0]:
	(c0, c1, c2) = (3, 1, 2)
	for i in range(N):
		if color[i] == -1:
			ans[i] = c0
			c0 += 3
	for i in range(N):
		if color[i] == 1:
			if c0 <= N:
				ans[i] = c0
				c0 += 3
			elif c1 <= N:
				ans[i] = c1
				c1 += 3
			else:
				ans[i] = c2
				c2 += 3
else:
	(c0, c1, c2) = (3, 1, 2)
	for i in range(N):
		if color[i] == 1:
			if c1 <= N:
				ans[i] = c1
				c1 += 3
			else:
				ans[i] = c0
				c0 += 3
	for i in range(N):
		if color[i] == -1:
			if c0 <= N:
				ans[i] = c0
				c0 += 3
			else:
				ans[i] = c2
				c2 += 3
print(*ans)


from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda : False))
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a][b] = True
	edges[b][a] = True
nums = [deque() for _ in range(3)]
for i in range(1, n + 1):
	nums[i % 3].append(i)
color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]

def coloring(num, pre_color):
	if pre_color:
		col = 0
	else:
		col = 1
	color[num - 1] = col
	cnts[col] += 1
	for k in edges[num].keys():
		if color[k - 1] == -1:
			coloring(k, col)
coloring(1, 1)
ans = [0 for _ in range(n)]

def solve(v):
	for i in range(n):
		if color[i] == v:
			ans[i] = nums[0].pop()
		else:
			for j in [1, 2, 0]:
				if len(nums[j]) > 0:
					ans[i] = nums[j].pop()
					break
if cnts[0] <= n // 3:
	solve(0)
elif cnts[1] <= n // 3:
	solve(1)
else:
	for i in range(n):
		if color[i]:
			if len(nums[1]) > 0:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[0].pop()
		elif len(nums[2]) > 0:
			ans[i] = nums[2].pop()
		else:
			ans[i] = nums[0].pop()
print(' '.join(list(map(str, ans))))


from collections import defaultdict, deque, Counter
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())
N = inp()
lines = defaultdict(set)
for _ in range(N - 1):
	(a, b) = inpl()
	a -= 1
	b -= 1
	lines[a].add(b)
	lines[b].add(a)
depths = [set() for _ in range(N)]
Ev = 0
Od = 0

def dfs(s, b, d):
	global depths
	global Ev
	global Od
	depths[d].add(s)
	if d % 2 == 0:
		Ev += 1
	else:
		Od += 1
	for t in lines[s]:
		if t == b:
			continue
		else:
			dfs(t, s, d + 1)
dfs(0, -1, 0)
n1 = (N + 2) // 3
n2 = (N + 1) // 3
n0 = (N + 0) // 3
ansl = [-1] * N
if Ev <= n0 or Od <= n0:
	if Ev <= n0:
		fl = 0
	else:
		fl = 1
	for (d, ps) in enumerate(depths):
		if d % 2 == fl:
			for p in ps:
				ansl[p] = n0 * 3
				n0 -= 1
		else:
			for p in ps:
				if n1 > 0:
					ansl[p] = n1 * 3 - 2
					n1 -= 1
				elif n2 > 0:
					ansl[p] = n2 * 3 - 1
					n2 -= 1
				else:
					ansl[p] = n0 * 3
					n0 -= 1
else:
	for (d, ps) in enumerate(depths):
		if d % 2 == 0:
			for p in ps:
				if n1 > 0:
					ansl[p] = n1 * 3 - 2
					n1 -= 1
				else:
					ansl[p] = n0 * 3
					n0 -= 1
		else:
			for p in ps:
				if n2 > 0:
					ansl[p] = n2 * 3 - 1
					n2 -= 1
				else:
					ansl[p] = n0 * 3
					n0 -= 1
print(' '.join(map(str, ansl)))


import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
	N = int(input())
	edge = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
	use = [-1 for _ in range(N)]
	d = [[0], []]
	use[0] = 0
	q = deque([0])
	while q:
		now = q.popleft()
		for fol in edge[now]:
			if use[fol] == -1:
				use[fol] = (use[now] + 1) % 2
				q.append(fol)
				d[use[fol]].append(fol)
	ans = [0 for _ in range(N)]
	b = [False for _ in range(N)]
	if len(d[0]) <= N // 3:
		l = len(d[0])
		for i in range(l):
			ans[d[0][i]] = 3 * i + 3
			b[3 * i + 2] = True
		t = 0
		for num in d[1]:
			while b[t]:
				t += 1
			ans[num] = t + 1
			b[t] = True
	elif len(d[1]) <= N // 3:
		l = len(d[1])
		for i in range(l):
			ans[d[1][i]] = 3 * i + 3
			b[3 * i + 2] = True
		t = 0
		for num in d[0]:
			while b[t]:
				t += 1
			ans[num] = t + 1
			b[t] = True
	else:
		l = len(d[0])
		t = 0
		for i in range(l):
			if i < (N - 1) // 3 + 1:
				ans[d[0][i]] = 3 * i + 1
				b[3 * i] = True
			else:
				ans[d[0][i]] = 3 * t + 3
				b[3 * t + 2] = True
				t += 1
		l = len(d[1])
		for i in range(l):
			if i < (N - 2) // 3 + 1:
				ans[d[1][i]] = 3 * i + 2
				b[3 * i + 1] = True
			else:
				ans[d[1][i]] = 3 * t + 3
				b[3 * t + 2] = True
				t += 1
	print(*ans)
main()


import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		G[a].append(b)
		G[b].append(a)
	(red, black) = (list(), list())
	visited = [False] * N
	stack = [(0, True)]
	visited[0] = True
	while stack:
		(v, is_red) = stack.pop()
		if is_red:
			red.append(v)
		else:
			black.append(v)
		for to in G[v]:
			if visited[to]:
				continue
			visited[to] = True
			stack.append((to, not is_red))
	if len(red) < len(black):
		(red, black) = (black, red)
	ans = [0] * N
	if len(black) <= N // 3:
		n3 = 3
		for v in black:
			(ans[v], n3) = (n3, n3 + 3)
		n = 1
		for v in red:
			if n3 <= N:
				(ans[v], n3) = (n3, n3 + 3)
			else:
				(ans[v], n) = (n, n + 1)
				if n % 3 == 0:
					n += 1
	else:
		(n1, n2, n3) = (1, 2, 3)
		for v in black:
			if n1 <= N:
				(ans[v], n1) = (n1, n1 + 3)
			else:
				(ans[v], n3) = (n3, n3 + 3)
		for v in red:
			if n2 <= N:
				(ans[v], n2) = (n2, n2 + 3)
			else:
				(ans[v], n3) = (n3, n3 + 3)
	print(*ans)
main()


import sys

def part(s, links):
	grp = [set(), set()]
	q = [(s, -1, 0)]
	while q:
		(v, p, g) = q.pop()
		grp[g].add(v)
		for u in links[v]:
			if u == p:
				continue
			q.append((u, v, g ^ 1))
	return grp

def solve(n, links):
	grp = part(0, links)
	can = [[], [], []]
	for i in range(1, n + 1):
		can[i % 3].append(i)
	if len(grp[0]) > len(grp[1]):
		(grp[0], grp[1]) = (grp[1], grp[0])
	if len(can[1]) > len(can[2]):
		(can[1], can[2]) = (can[2], can[1])
	ans = [0] * n
	if len(grp[0]) <= len(can[0]):
		for (i, v) in enumerate(grp[0]):
			ans[v] = can[0].pop()
		can = can[0] + can[1] + can[2]
		for (i, v) in enumerate(grp[1]):
			ans[v] = can.pop()
		return ans
	for (i, v) in enumerate(grp[0]):
		if can[1]:
			ans[v] = can[1].pop()
		else:
			ans[v] = can[0].pop()
	for (i, v) in enumerate(grp[1]):
		if can[2]:
			ans[v] = can[2].pop()
		else:
			ans[v] = can[0].pop()
	return ans
n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
	(a, b) = map(int, line.split())
	a -= 1
	b -= 1
	links[a].add(b)
	links[b].add(a)
print(*solve(n, links))


from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
v = [-1] * n
v[0] = 0
q = deque([0])
while q:
	p = q.popleft()
	for i in g[p]:
		if v[i] == -1:
			v[i] = 1 - v[p]
			q.append(i)
z = 0
for i in v:
	if i == 0:
		z += 1
ans = [0] * n
if z <= n // 3:
	j = 3
	for i in range(n):
		if v[i] == 0:
			ans[i] = j
			j += 3
	j = 1
	for i in range(n):
		if ans[i] == 0:
			ans[i] = j
			j += 1
			if j % 3 == 0 and j // 3 <= z:
				j += 1
	print(*ans)
elif n - z <= n // 3:
	j = 3
	for i in range(n):
		if v[i] == 1:
			ans[i] = j
			j += 3
	j = 1
	for i in range(n):
		if ans[i] == 0:
			ans[i] = j
			j += 1
			if j % 3 == 0 and j // 3 <= n - z:
				j += 1
	print(*ans)
else:
	o = 1
	t = 2
	tt = 3
	for i in range(n):
		if v[i] == 0 and o <= n:
			ans[i] = o
			o += 3
		elif v[i] == 0:
			ans[i] = tt
			tt += 3
		if v[i] == 1 and t <= n:
			ans[i] = t
			t += 3
		elif v[i] == 1:
			ans[i] = tt
			tt += 3
	print(*ans)


def main():
	N = int(input())
	ab = [tuple(map(int, input().split())) for _ in range(N - 1)]
	to = [[] for _ in range(N)]
	for (a, b) in ab:
		to[a - 1].append(b - 1)
		to[b - 1].append(a - 1)
	c1 = list(range(1, N + 1, 3))
	c2 = list(range(2, N + 1, 3))
	c3 = list(range(3, N + 1, 3))
	color = [0] * N
	for root in range(N):
		if len(to[root]) == 1:
			break
	queue = set([root])
	color[root] = 1
	while queue:
		v = queue.pop()
		color_v = color[v]
		for i in to[v]:
			if color[i] == 0:
				color[i] = 3 - color_v
				queue.add(i)
	ans = [0] * N
	order = sorted(range(N), key=lambda x: color[x])
	if color.count(1) <= N / 3:
		for i in order:
			if c3:
				ans[i] = c3.pop(-1)
			elif c1:
				ans[i] = c1.pop(-1)
			else:
				ans[i] = c2.pop(-1)
	elif color.count(2) <= N / 3:
		for i in reversed(order):
			if c3:
				ans[i] = c3.pop(-1)
			elif c1:
				ans[i] = c1.pop(-1)
			else:
				ans[i] = c2.pop(-1)
	else:
		for i in range(N):
			if color[i] == 1 and c1:
				ans[i] = c1.pop(-1)
			elif color[i] == 2 and c2:
				ans[i] = c2.pop(-1)
			else:
				ans[i] = c3.pop(-1)
	print(*ans)
main()


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)]
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()
		elif 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()
		elif mod1:
			node_p[i] = mod1.pop()
		elif mod2:
			node_p[i] = mod2.pop()
		else:
			node_p[i] = mod0.pop()
	elif dist[i] % 2 == 0:
		if mod1:
			node_p[i] = mod1.pop()
		elif mod0:
			node_p[i] = mod0.pop()
		else:
			print(-1)
			exit(0)
	elif mod2:
		node_p[i] = mod2.pop()
	elif mod0:
		node_p[i] = mod0.pop()
	else:
		print(-1)
		exit(0)
	print(node_p[i], end=' ')
odd = 0
even = 0
bfs(N)
for i in range(1, N + 1):
	if dist[i] % 2 == 0:
		even += 1
	else:
		odd += 1
for k in range(1, N + 1):
	modfit(k)
print()


def main():
	from collections import deque
	from itertools import chain
	import sys
	input = sys.stdin.readline
	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)
	bipartite = [-1] * N
	bipartite[0] = 0
	dq = deque([0])
	while dq:
		v = dq.popleft()
		nb = bipartite[v] ^ 1
		for u in graph[v]:
			if ~bipartite[u]:
				continue
			bipartite[u] = nb
			dq.append(u)
	s0 = bipartite.count(0)
	s1 = N - s0
	it1 = iter(range(1, N + 1, 3))
	it2 = iter(range(2, N + 1, 3))
	it3 = iter(range(3, N + 1, 3))
	it123 = chain(it1, it2, it3)
	it13 = chain(it1, it3)
	it23 = chain(it2, it3)
	ans = [-1] * N
	K = N // 3
	if s0 <= K:
		for v in range(N):
			if bipartite[v] == 0:
				ans[v] = next(it3)
			else:
				ans[v] = next(it123)
	elif s1 <= K:
		for v in range(N):
			if bipartite[v] == 1:
				ans[v] = next(it3)
			else:
				ans[v] = next(it123)
	else:
		for v in range(N):
			if bipartite[v] == 0:
				ans[v] = next(it13)
			else:
				ans[v] = next(it23)
	print(*ans)
main()


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
ed = [tuple(map(int, input().split())) for _ in range(n - 1)]
g = [list() for _ in range(n)]
for (a, b) in ed:
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
bi = [0] * n

def dfs(v, p):
	for x in g[v]:
		if x == p:
			continue
		bi[x] = 1 - bi[v]
		dfs(x, v)
	return
dfs(0, -1)
one = sum(bi)
two = n - one
if one < two:
	(one, two) = (two, one)
	bi = [1 - x for x in bi]
on = 1
tw = 2
th = 3
ans = [0] * n
if two <= n // 3:
	for i in range(n):
		if bi[i]:
			if on > n and tw > n:
				ans[i] = th
				th += 3
			elif on > n:
				ans[i] = tw
				tw += 3
			else:
				ans[i] = on
				on += 3
		else:
			ans[i] = th
			th += 3
	print(*ans)
	exit(0)
for i in range(n):
	if bi[i]:
		if on > n:
			ans[i] = th
			th += 3
		else:
			ans[i] = on
			on += 3
	elif tw > n:
		ans[i] = th
		th += 3
	else:
		ans[i] = tw
		tw += 3
print(*ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
inf = float('inf')
prv = [inf] * n
prv[0] = -1
depth = [inf] * n
depth[0] = 0
stack = [0]
while stack:
	cur = stack.pop()
	for next in edge[cur]:
		if prv[next] == inf:
			prv[next] = cur
			depth[next] = depth[cur] + 1
			stack.append(next)
(e, o) = (0, 0)
for i in range(n):
	if depth[i] % 2:
		o += 1
	else:
		e += 1
Ans = [0] * n
if e <= n // 3:
	(ct1, ct2, ct3) = (0, 0, 0)
	for i in range(n):
		if not depth[i] % 2:
			Ans[i] = 3 * ct3 + 3
			ct3 += 1
		elif 3 * ct2 + 2 <= n:
			Ans[i] = 3 * ct2 + 2
			ct2 += 1
		elif 3 * ct1 + 1 <= n:
			Ans[i] = 3 * ct1 + 1
			ct1 += 1
		else:
			Ans[i] = 3 * ct3 + 3
			ct3 += 1
elif o <= n // 3:
	(ct1, ct2, ct3) = (0, 0, 0)
	for i in range(n):
		if depth[i] % 2:
			Ans[i] = 3 * ct3 + 3
			ct3 += 1
		elif 3 * ct1 + 1 <= n:
			Ans[i] = 3 * ct1 + 1
			ct1 += 1
		elif 3 * ct2 + 2 <= n:
			Ans[i] = 3 * ct2 + 2
			ct2 += 1
		else:
			Ans[i] = 3 * ct3 + 3
			ct3 += 1
else:
	(ct1, ct2, ct3) = (0, 0, 0)
	for i in range(n):
		if not depth[i] % 2:
			if 3 * ct1 + 1 <= n:
				Ans[i] = 3 * ct1 + 1
				ct1 += 1
			else:
				Ans[i] = 3 * ct3 + 3
				ct3 += 1
		elif 3 * ct2 + 2 <= n:
			Ans[i] = 3 * ct2 + 2
			ct2 += 1
		else:
			Ans[i] = 3 * ct3 + 3
			ct3 += 1
print(*Ans)


import sys
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
Cl = [-1] * N
C = [[0], []]
q = [0]
c = 0
Cl[0] = 0
while q:
	qq = []
	c ^= 1
	for p in q:
		for np in graph[p]:
			if Cl[np] == -1:
				Cl[np] = c
				C[c].append(np)
				qq.append(np)
	q = qq
if len(C[0]) > len(C[1]):
	C = [C[1], C[0]]
c0 = (N + 2) // 3
c1 = (N + 1) // 3
c2 = N // 3
Co = [[], [], []]
if len(C[0]) < c1:
	R = set(C[0])
	for r in R:
		Co[2].append(r)
	for p in range(N):
		if p in R:
			continue
		elif len(Co[0]) < c0:
			Co[0].append(p)
		elif len(Co[1]) < c1:
			Co[1].append(p)
		else:
			Co[2].append(p)
else:
	R2 = set(C[1])
	for p in range(N):
		if p in R2:
			if len(Co[0]) < c0:
				Co[0].append(p)
			else:
				Co[2].append(p)
		elif len(Co[1]) < c1:
			Co[1].append(p)
		else:
			Co[2].append(p)
ans = [None] * N
for (i, n) in enumerate(Co[0]):
	ans[n] = 3 * i + 1
for (i, n) in enumerate(Co[1]):
	ans[n] = 3 * i + 2
for (i, n) in enumerate(Co[2]):
	ans[n] = 3 * i + 3
print(*ans)


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
adj = [[] for _ in range(n)]
for (a, b) in ab:
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)

class Tree:
	WHITE = 0
	GRAY = -1
	BLACK = 1

	def __init__(self, adj):
		n = len(adj)
		self.adj = adj
		self.colors = [self.WHITE] * n
		self.depths = [-1] * n
		self.depth = 0

	def init(self):
		self.__init__(self.adj)

	def dfs(self, u):
		if self.colors[u] == self.BLACK:
			return
		self.colors[u] = self.GRAY
		self.depths[u] = self.depth
		for v in self.adj[u]:
			if self.colors[v] == self.WHITE:
				self.depth += 1
				self.dfs(v)
				self.depth -= 1
		self.colors[u] = self.BLACK
tree = Tree(adj)
tree.dfs(0)
ev = [i for (i, e) in enumerate(tree.depths) if e % 2 == 0]
od = [i for (i, e) in enumerate(tree.depths) if e % 2]
l_ev = len(ev)
l_od = len(od)
mod0 = [e for e in range(1, n + 1) if e % 3 == 0]
mod1 = [e for e in range(1, n + 1) if e % 3 == 1]
mod2 = [e for e in range(1, n + 1) if e % 3 == 2]
ans = [0] * n

def f(li1, li2):
	while li1 and li2:
		i = li1.pop()
		num = li2.pop()
		ans[i] = num
if l_ev > n / 3 and l_od > n / 3:
	f(ev, mod1)
	f(od, mod2)
	f(ev, mod0)
	f(od, mod0)
elif l_ev <= n / 3:
	f(ev, mod0)
	f(od, mod0)
	f(od, mod1)
	f(od, mod2)
else:
	f(od, mod0)
	f(ev, mod0)
	f(ev, mod1)
	f(ev, mod2)
print(*ans)


import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

class Tree:

	def __init__(self, v):
		self.v = v
		self.neighbors = []

	def set_rank(self, rank, parent):
		self.rank = rank
		for neighbor in self.neighbors:
			if neighbor is parent:
				continue
			neighbor.set_rank(rank=rank + 1, parent=self)
trees = {i: Tree(i) for i in range(1, N + 1)}
for (a, b) in AB:
	trees[a].neighbors.append(trees[b])
	trees[b].neighbors.append(trees[a])
try:
	trees[1].set_rank(1, None)
except:
	print(-1)
	exit()
group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
	x[i % 3].add(i)
if len(group1) < len(group0):
	(group1, group0) = (group0, group1)
result = {}
if len(group0) <= len(x[0]):
	while group0 and x[0]:
		result[group0.pop()] = x[0].pop()
	y = x[0] | x[1] | x[2]
	while group1 and y:
		result[group1.pop()] = y.pop()
else:
	while x[2] and group0:
		result[group0.pop()] = x[2].pop()
	while x[1] and group1:
		result[group1.pop()] = x[1].pop()
	while group0 and x[0]:
		result[group0.pop()] = x[0].pop()
	while group1 and x[0]:
		result[group1.pop()] = x[0].pop()
	if group0 or group1:
		print(-1)
		exit()
print(' '.join((str(result[i]) for i in range(1, N + 1))))


n = int(input())
con = [set() for _ in range(n)]
tree = [0] * n
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	con[a - 1].add(b)
	con[b - 1].add(a)
checked = set([1])
stack = list(con[0])
stack_ = []
while len(checked) < n:
	while stack:
		x = stack.pop()
		if x in checked:
			continue
		checked.add(x)
		stack_.extend(con[x - 1])
		tree[x - 1] = 1
	while stack_:
		x = stack_.pop()
		if x in checked:
			continue
		checked.add(x)
		stack.extend(con[x - 1])
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
	if (i + 1) % 3 == 0:
		mod0.append(i + 1)
	elif (i + 1) % 3 == 1:
		mod1.append(i + 1)
	else:
		mod2.append(i + 1)
ans = [0] * n
sum_tree = sum(tree)
if sum_tree < n / 3:
	for i in range(n):
		if tree[i] == 0:
			if mod1:
				ans[i] = mod1.pop()
			elif mod2:
				ans[i] = mod2.pop()
			else:
				ans[i] = mod0.pop()
		else:
			ans[i] = mod0.pop()
elif sum_tree > n * 2 / 3:
	for i in range(n):
		if tree[i] == 1:
			if mod1:
				ans[i] = mod1.pop()
			elif mod2:
				ans[i] = mod2.pop()
			else:
				ans[i] = mod0.pop()
		else:
			ans[i] = mod0.pop()
else:
	for i in range(n):
		if tree[i] == 0:
			if mod1:
				ans[i] = mod1.pop()
			else:
				ans[i] = mod0.pop()
		elif mod2:
			ans[i] = mod2.pop()
		else:
			ans[i] = mod0.pop()
print(' '.join(map(lambda x: str(x), ans)))


import sys
sys.setrecursionlimit(10 ** 5 + 1)

def cur(p):
	for i in x[p]:
		if rank[i] == -1:
			rank[i] = rank[p] + 1
			par[i] = p
			cur(i)
n = int(input())
x = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	x[a].append(b)
	x[b].append(a)
rank = [-1 for i in range(n)]
rank[0] = 0
par = [-1 for i in range(n)]
cur(0)
M = max(rank)
x = [[] for i in range(M + 1)]
q = [0, 0]
r = [n // 3, n // 3, n // 3]
if n % 3 > 0:
	r[1] += 1
if n % 3 > 1:
	r[2] += 1
(tmp1, tmp2, tmp3) = (1, 2, 3)
for i in range(n):
	q[rank[i] % 2] += 1
	x[rank[i]].append(i)
ans = [-1 for i in range(n)]
if q[0] <= r[0] + r[1] and q[1] <= r[0] + r[2]:
	for i in range(n):
		if rank[i] % 2 == 0:
			if tmp1 <= n:
				ans[i] = tmp1
				tmp1 += 3
			else:
				ans[i] = tmp3
				tmp3 += 3
		elif tmp2 <= n:
			ans[i] = tmp2
			tmp2 += 3
		else:
			ans[i] = tmp3
			tmp3 += 3
elif q[0] <= r[0]:
	for i in range(n):
		if rank[i] % 2 == 0:
			ans[i] = tmp3
			tmp3 += 3
		elif tmp1 <= n:
			ans[i] = tmp1
			tmp1 += 3
		elif tmp2 <= n:
			ans[i] = tmp2
			tmp2 += 3
		else:
			ans[i] = tmp3
			tmp3 += 3
elif q[1] <= r[0]:
	for i in range(n):
		if rank[i] % 2 == 1:
			ans[i] = tmp3
			tmp3 += 3
		elif tmp1 <= n:
			ans[i] = tmp1
			tmp1 += 3
		elif tmp2 <= n:
			ans[i] = tmp2
			tmp2 += 3
		else:
			ans[i] = tmp3
			tmp3 += 3
for i in range(n - 1):
	print(ans[i], end=' ')
print(ans[n - 1])


N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	T[a].append(b)
	T[b].append(a)
colors = [-1] * N
stack = [(0, 0)]
while stack:
	(n, color) = stack.pop()
	colors[n] = color
	for to in T[n]:
		if colors[to] != -1:
			continue
		stack.append((to, color ^ 1))
X = [[] for _ in range(3)]
for n in range(1, N + 1):
	X[n % 3].append(n)
X.append(X[0])
del X[0]
ans = []
(x12, x3) = (X[0] + X[1], X[2])
if colors.count(0) <= N // 3:
	for color in colors:
		if color == 0:
			ans.append(x3.pop())
		elif x12:
			ans.append(x12.pop())
		else:
			ans.append(x3.pop())
elif colors.count(1) <= N // 3:
	for color in colors:
		if color == 1:
			ans.append(x3.pop())
		elif x12:
			ans.append(x12.pop())
		else:
			ans.append(x3.pop())
else:
	for color in colors:
		if X[color]:
			ans.append(X[color].pop())
		else:
			ans.append(X[2].pop())
print(' '.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for _ in range(n)]
ans = [-1] * n
odd = []
even = []
nums = [[], [], []]
for i in range(1, n + 1):
	nums[i % 3].append(i)

def dfs(v, p=-1, d=0):
	if d % 2:
		odd.append(v)
	else:
		even.append(v)
	for nv in g[v]:
		if nv == p:
			continue
		dfs(nv, v, d + 1)
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)
zerocnt = len(nums[0])
if len(even) <= zerocnt:
	for even_node in even:
		ans[even_node] = nums[0].pop()
	rest = nums[0] + nums[1] + nums[2]
	for odd_node in odd:
		ans[odd_node] = rest.pop()
elif len(odd) <= zerocnt:
	for odd_node in odd:
		ans[odd_node] = nums[0].pop()
	rest = nums[0] + nums[1] + nums[2]
	for even_node in even:
		ans[even_node] = rest.pop()
else:
	for odd_node in odd:
		if len(nums[1]) != 0:
			ans[odd_node] = nums[1].pop()
		else:
			ans[odd_node] = nums[0].pop()
	for even_node in even:
		if len(nums[2]) != 0:
			ans[even_node] = nums[2].pop()
		else:
			ans[even_node] = nums[0].pop()
print(*ans)


import sys
input = sys.stdin.buffer.readline
from collections import deque
from collections import defaultdict

def main():
	N = int(input())
	M = N - 1
	G = defaultdict(set)
	color = [0 for i in range(N + 1)]
	for _ in range(M):
		(A, B) = map(int, input().split())
		G[A].add(B)
		G[B].add(A)
	color[1] = 1
	que = deque([1])
	while len(que):
		p = que.popleft()
		for q in list(G[p]):
			if color[q] == 0:
				color[q] = -color[p]
				que.append(q)
	b = []
	w = []
	for i in range(1, N + 1):
		if color[i] == 1:
			b.append(i)
		else:
			w.append(i)
	ans = [0] * (N + 1)
	lim = (N - 1) // 3
	i = 0
	if len(b) < len(w):
		for val in w:
			if i <= lim:
				ans[val] = 3 * i + 1
				i += 1
			else:
				break
		w = w[i:]
	else:
		for val in b:
			if i <= lim:
				ans[val] = 3 * i + 1
				i += 1
			else:
				break
		b = b[i:]
	lim = (N - 2) // 3
	i = 0
	if len(b) < len(w):
		for val in w:
			if i <= lim:
				ans[val] = 3 * i + 2
				i += 1
			else:
				break
		w = w[i:]
	else:
		for val in b:
			if i <= lim:
				ans[val] = 3 * i + 2
				i += 1
			else:
				break
		b = b[i:]
	i = 0
	for val in b:
		ans[val] = 3 * i + 3
		i += 1
	for val in w:
		ans[val] = 3 * i + 3
		i += 1
	print(*ans[1:])
main()


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
adj_list = [[] for _ in range(N + 1)]
for (a, b) in ab:
	adj_list[a].append(b)
	adj_list[b].append(a)
group = [1] * (N + 1)
group[0] = -1

def dfs(v, par, grp):
	nxt_grp = grp ^ 3
	for child in adj_list[v]:
		if child == par:
			continue
		group[child] = nxt_grp
		dfs(child, v, nxt_grp)
	return
dfs(1, -1, 1)
ans = [0] * (N + 1)
used = [False] * (N + 1)
group_num = [0] * 2
for g in group[1:]:
	group_num[g - 1] += 1
if min(group_num) <= N // 3:
	if min(group_num) == group_num[0]:
		minidx = 1
	else:
		minidx = 2
	idx = 3
	idx_n = 1
	for (i, g) in enumerate(group):
		if i == 0:
			continue
		if g == minidx:
			ans[i] = idx
			used[idx] = True
			idx += 3
	for (i, g) in enumerate(group):
		if i == 0:
			continue
		if ans[i] != 0:
			continue
		while used[idx_n]:
			idx_n += 1
		ans[i] = idx_n
		used[idx_n] = True
		idx_n += 1
	print(*ans[1:])
else:
	idx_1 = 1
	idx_2 = 2
	for (i, g) in enumerate(group):
		if i == 0:
			continue
		if g == 1:
			if idx_1 > N:
				continue
			ans[i] = idx_1
			used[idx_1] = True
			idx_1 += 3
		else:
			if idx_2 > N:
				continue
			ans[i] = idx_2
			used[idx_2] = True
			idx_2 += 3
	idx = 3
	for i in range(1, N + 1):
		if ans[i] == 0:
			while used[idx]:
				idx += 3
			ans[i] = idx
			used[idx] = True
	print(*ans[1:])


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
cl = [0] * (N + 1)
vis = set()

def dfs(x):
	global cl
	global vis
	vis.add(x)
	for y in e[x]:
		if y in vis:
			continue
		cl[y] = (cl[x] + 1) % 2
		dfs(y)
dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1):
	nm[i % 3].append(i)
if bl <= N // 3:
	for i in range(1, N + 1):
		if cl[i]:
			res[i] = nm[0].pop()
		elif len(nm[1]):
			res[i] = nm[1].pop()
		elif len(nm[2]):
			res[i] = nm[2].pop()
		else:
			res[i] = nm[0].pop()
	print(*res[1:])
	exit(0)
if wh <= N // 3:
	for i in range(1, N + 1):
		if cl[i] == 0:
			res[i] = nm[0].pop()
		elif len(nm[1]):
			res[i] = nm[1].pop()
		elif len(nm[2]):
			res[i] = nm[2].pop()
		else:
			res[i] = nm[0].pop()
	print(*res[1:])
	exit(0)
f = 0
for i in range(1, N + 1):
	if cl[i]:
		if len(nm[1]):
			res[i] = nm[1].pop()
		else:
			res[i] = nm[0].pop()
	elif len(nm[2]):
		res[i] = nm[2].pop()
	else:
		res[i] = nm[0].pop()
print(*res[1:])


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
mod_0 = []
mod_1 = []
mod_2 = []
for i in range(1, n + 1):
	if i % 3 == 0:
		mod_0.append(i)
	elif i % 3 == 1:
		mod_1.append(i)
	else:
		mod_2.append(i)
ans = [-1] * n
from collections import deque

def bfs(u):
	queue = deque([u])
	d = [None] * n
	d[u] = 0
	while queue:
		v = queue.popleft()
		for i in g[v]:
			if d[i] is None:
				d[i] = d[v] + 1
				queue.append(i)
	return d
d = bfs(0)
cnt = [[] for _ in range(2)]
for i in range(n):
	if d[i] % 2 == 0:
		cnt[0].append(i + 1)
	elif d[i] % 2 == 1:
		cnt[1].append(i + 1)
cnt = sorted(cnt, key=lambda x: len(x))
if len(mod_0) >= len(cnt[0]):
	for i in range(len(cnt[0])):
		ans[cnt[0][i] - 1] = mod_0.pop()
	for i in range(len(cnt[1])):
		if mod_0:
			ans[cnt[1][i] - 1] = mod_0.pop()
		elif mod_1:
			ans[cnt[1][i] - 1] = mod_1.pop()
		else:
			ans[cnt[1][i] - 1] = mod_2.pop()
	print(*ans)
	sys.exit()
for i in range(2):
	c = cnt[i]
	for j in range(len(c)):
		if mod_2 and i == 0:
			ans[cnt[i][j] - 1] = mod_2.pop()
		elif mod_1 and i == 1:
			ans[cnt[i][j] - 1] = mod_1.pop()
		elif mod_0:
			ans[cnt[i][j] - 1] = mod_0.pop()
		else:
			print(-1)
			sys.exit()
print(*ans)


from collections import deque
import sys
input = sys.stdin.buffer.readline
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(fr, to) = map(lambda a: int(a) - 1, input().split())
	edges[fr].append(to)
	edges[to].append(fr)
dist = [10 ** 10] * N
que = deque([(0, 0)])
while que:
	(now, d) = que.popleft()
	if dist[now] <= d:
		continue
	dist[now] = d
	for to in edges[now]:
		que.append((to, d + 1))
A = [i for (i, d) in enumerate(dist) if d % 2 == 0]
B = [i for (i, d) in enumerate(dist) if d % 2 == 1]
if len(A) > len(B):
	(A, B) = (B, A)
ans = [-1] * N
nums = set(range(1, N + 1))
if len(A) <= N // 3:
	mul = 1
	for i in A:
		ans[i] = 3 * mul
		nums.remove(3 * mul)
		mul += 1
	nums = list(nums)
	for (i, n) in zip(B, nums):
		ans[i] = n
else:
	mul = 1
	for (c, i) in enumerate(A):
		if c * 3 + 1 > N:
			ans[i] = mul * 3
			mul += 1
		else:
			ans[i] = c * 3 + 1
	for (c, i) in enumerate(B):
		if c * 3 + 2 > N:
			ans[i] = mul * 3
			mul += 1
		else:
			ans[i] = c * 3 + 2
print(*ans)


from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
num = [-1] * N
q = deque()
q.append((0, 0))
num[0] = 0
while q:
	temp = q.popleft()
	u = temp[0]
	n = temp[1]
	for v in E[u]:
		if num[v] >= 0:
			continue
		num[v] = (n + 1) % 2
		q.append((v, (n + 1) % 2))
ans = [0] * N
if sum(num) <= N // 3 or N - sum(num) <= N // 3:
	f = 1
	if N - sum(num) <= N // 3:
		f = 0
	s = 1
	t = 3
	for i in range(N):
		if num[i] == f:
			ans[i] = t
			t += 3
	for i in range(N):
		if ans[i] == 0:
			ans[i] = s
			s += 1
			if s % 3 == 0 and s < t:
				s += 1
else:
	s = 1
	t = 2
	u = 3
	for i in range(N):
		if num[i] == 0 and s <= N:
			ans[i] = s
			s += 3
		elif num[i] == 1 and t <= N:
			ans[i] = t
			t += 3
		else:
			ans[i] = u
			u += 3
print(*ans)


import sys
input = sys.stdin.readline
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
COLOR = [-1] * (N + 1)
Q = [1]
COLOR[1] = 1
while Q:
	x = Q.pop()
	for to in E[x]:
		if COLOR[to] == -1:
			COLOR[to] = 1 - COLOR[x]
			Q.append(to)
A1 = N // 3
A2 = N // 3
A3 = N // 3
if N % 3 == 1:
	A1 += 1
elif N % 3 == 2:
	A1 += 1
	A2 += 1
S1 = COLOR.count(1)
S2 = COLOR.count(0)
SA = A1 + A3 - A2
if abs(S1 - S2) <= SA:
	ANS = [0] * (N + 1)
	now1 = 1
	now2 = 2
	if S1 < S2:
		for i in range(1, N + 1):
			if COLOR[i] == 1:
				ANS[i] = now2
				now2 += 3
			else:
				ANS[i] = now1
				now1 += 3
	else:
		for i in range(1, N + 1):
			if COLOR[i] == 0:
				ANS[i] = now2
				now2 += 3
			else:
				ANS[i] = now1
				now1 += 3
	now3 = 3
	for i in range(1, N + 1):
		if ANS[i] > N:
			ANS[i] = now3
			now3 += 3
	print(*ANS[1:])
else:
	ANS = [0] * (N + 1)
	now1 = 1
	now2 = 2
	now3 = 3
	if S1 < S2:
		for i in range(1, N + 1):
			if COLOR[i] == 1:
				ANS[i] = now3
				now3 += 3
	else:
		for i in range(1, N + 1):
			if COLOR[i] == 0:
				ANS[i] = now3
				now3 += 3
	for i in range(1, N + 1):
		if ANS[i] == 0:
			if now1 <= N:
				ANS[i] = now1
				now1 += 3
			elif now2 <= N:
				ANS[i] = now2
				now2 += 3
			else:
				ANS[i] = now3
				now3 += 3
	print(*ANS[1:])


n = int(input())
ab = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ab[a - 1].append(b - 1)
	ab[b - 1].append(a - 1)
rb = [-1] * n
rb[0] = 1
count1 = 1
count2 = 0
rb_m = [[0]]
for i in rb_m:
	n_rb = []
	for j in i:
		x = rb[j]
		for k in ab[j]:
			if rb[k] != -1:
				continue
			if x == 1:
				rb[k] = 2
				count2 += 1
			elif x == 2:
				rb[k] = 1
				count1 += 1
			n_rb.append(k)
	set(n_rb)
	if n_rb == []:
		break
	else:
		rb_m.append(n_rb)
ans = [0 for i in range(n)]
if count1 > n // 3 and count2 > n // 3:
	ne1 = 1
	ne2 = 2
	ne3 = 3
	for i in range(n):
		if rb[i] == 1 and ne1 <= n:
			ans[i] = ne1
			ne1 += 3
		elif rb[i] == 2 and ne2 <= n:
			ans[i] = ne2
			ne2 += 3
		else:
			ans[i] = ne3
			ne3 += 3
elif count2 >= 2 * n // 3:
	ne1 = 1
	ne2 = 2
	ne3 = 3
	for i in range(n):
		if rb[i] == 1:
			ans[i] = ne3
			ne3 += 3
		elif ne1 <= n:
			ans[i] = ne1
			ne1 += 3
		elif ne2 <= n:
			ans[i] = ne2
			ne2 += 3
		else:
			ans[i] = ne3
			ne3 += 3
elif count1 >= 2 * n // 3:
	ne1 = 1
	ne2 = 2
	ne3 = 3
	for i in range(n):
		if rb[i] == 2:
			ans[i] = ne3
			ne3 += 3
		elif ne1 <= n:
			ans[i] = ne1
			ne1 += 3
		elif ne2 <= n:
			ans[i] = ne2
			ne2 += 3
		else:
			ans[i] = ne3
			ne3 += 3
print(*ans)


from collections import deque

def solve(n, ab_list):
	g = [[] for _ in range(n + 1)]
	for (a, b) in ab_list:
		g[a].append(b)
		g[b].append(a)
	d_list = [-1] * (n + 1)
	d_list[1] = 0
	queue = deque([1])
	while len(queue) > 0:
		p = queue.popleft()
		for q in g[p]:
			if d_list[q] == -1:
				d_list[q] = d_list[p] + 1
				queue.append(q)
	cnt_2 = [0] * 6
	for i in range(1, n + 1):
		cnt_2[d_list[i] % 2] += 1
	if cnt_2[0] <= cnt_2[1]:
		min_01 = 0
	else:
		min_01 = 1
	min_sum = cnt_2[min_01]
	if min_sum <= n // 3:
		res_list = [0] * n
		list_3 = [3 * (k + 1) for k in range(min_sum)]
		list_other = [k for k in range(1, n + 1) if k % 3 != 0] + [3 * (k + 1) for k in range(min_sum, n // 3)]
		for i in range(1, n + 1):
			if d_list[i] % 2 == min_01:
				res_list[i - 1] = list_3.pop()
			else:
				res_list[i - 1] = list_other.pop()
	else:
		res_list = [0] * n
		add_1 = min_sum - (n + 2) // 3
		list_1 = [k + 1 for k in range(n) if k % 3 == 0] + [3 * (k + 1) for k in range(add_1)]
		list_2 = [k + 1 for k in range(n) if k % 3 == 1] + [3 * (k + 1) for k in range(add_1, n // 3)]
		for i in range(1, n + 1):
			if d_list[i] % 2 == min_01:
				res_list[i - 1] = list_1.pop()
			else:
				res_list[i - 1] = list_2.pop()
	return ' '.join([str(r) for r in res_list])

def main():
	n = int(input())
	ab_list = [list(map(int, input().split())) for _ in range(n - 1)]
	res = solve(n, ab_list)
	print(res)

def test():
	assert solve(5, [[1, 2], [1, 3], [3, 4], [3, 5]]) == '3 4 1 5 2'
main()


import sys
sys.setrecursionlimit(2 * 10 ** 6)

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

def dfs(n, d):
	if depth[n] != -1:
		return
	depth[n] = d
	for nn in eAB[n]:
		dfs(nn, d + 1)
	return
N = int(input())
AB = [inpl() for i in range(N - 1)]
eAB = [[] for i in range(N)]
for (a, b) in AB:
	eAB[a - 1].append(b - 1)
	eAB[b - 1].append(a - 1)
depth = [-1 for i in range(N)]
dfs(0, 0)
eo = [[], []]
for i in range(N):
	eo[depth[i] % 2].append(i)
ans = [-1 for i in range(N)]
if len(eo[0]) > N // 3 and len(eo[1]) > N // 3:
	for i in range(N // 3):
		ans[eo[0][i]] = 3 * i + 1
		ans[eo[1][i]] = 3 * i + 2
	t_0 = N // 3
	t_1 = N // 3
	if N % 3 > 0:
		ans[eo[0][N // 3]] = 3 * (N // 3) + 1
		t_0 += 1
	if N % 3 > 1:
		ans[eo[1][N // 3]] = 3 * (N // 3) + 2
		t_1 += 1
	for (i, v) in enumerate(eo[0][t_0:] + eo[1][t_1:]):
		ans[v] = 3 * (i + 1)
else:
	if len(eo[0]) <= N // 3:
		ni = 0
	else:
		ni = 1
	tmp = [True for i in range(N + 1)]
	for i in range(len(eo[ni])):
		ans[eo[ni][i]] = 3 * (i + 1)
		tmp[3 * (i + 1)] = False
	tmp = [i for (i, t) in enumerate(tmp) if t is True]
	j = 1
	for i in range(N):
		if ans[i] != -1:
			continue
		ans[i] = tmp[j]
		j += 1
print(' '.join(list(map(str, ans))))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
bigraph = [0] * n

def dfs(v, v_p, depth):
	bigraph[v] = depth % 2
	for v_next in graph[v]:
		if v_next == v_p:
			continue
		dfs(v_next, v, depth + 1)
dfs(0, -1, 1)
m1 = sum(bigraph)
m2 = n - m1
ans = [-1] * n
if m1 > n // 3 and m2 > n // 3:
	c1 = 1
	c2 = 2
	for i in range(n):
		if bigraph[i] == 0 and c1 <= n:
			ans[i] = c1
			c1 += 3
		if bigraph[i] == 1 and c2 <= n:
			ans[i] = c2
			c2 += 3
	c3 = 3
	for i in range(n):
		if ans[i] == -1:
			ans[i] = c3
			c3 += 3
elif m1 > m2:
	c1 = 1
	c2 = 2
	c3 = 3
	for i in range(n):
		if bigraph[i] == 0:
			ans[i] = c3
			c3 += 3
	for i in range(n):
		if ans[i] == -1:
			if c1 <= n:
				ans[i] = c1
				c1 += 3
			elif c2 <= n:
				ans[i] = c2
				c2 += 3
			else:
				ans[i] = c3
				c3 += 3
else:
	c1 = 1
	c2 = 2
	c3 = 3
	for i in range(n):
		if bigraph[i] == 1:
			ans[i] = c3
			c3 += 3
	for i in range(n):
		if ans[i] == -1:
			if c1 <= n:
				ans[i] = c1
				c1 += 3
			elif c2 <= n:
				ans[i] = c2
				c2 += 3
			else:
				ans[i] = c3
				c3 += 3
print(*ans)


import sys
readline = sys.stdin.buffer.readline

def dfs(s):
	stack = [s]
	used = set(s)
	dist = [0] * N
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf not in used:
				used.add(vf)
				dist[vf] = 1 + dist[vn]
				stack.append(vf)
N = int(readline())
zero = N // 3
one = N // 3 + int(N % 3 >= 1)
two = N - zero - one
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
root = 0
col = [0] * N
stack = [root]
used = set(stack)
while stack:
	vn = stack.pop()
	for vf in Edge[vn]:
		if vf not in used:
			used.add(vf)
			col[vf] = 1 - col[vn]
			stack.append(vf)
if 2 * sum(col) < N:
	col = [1 - c for c in col]
black = sum(col)
white = N - black
Ans = [None] * N
remain = set(range(1, N + 1))
if N <= 3:
	Ans = list(range(1, N + 1))
elif white <= zero:
	zb = [i for i in range(1, N + 1) if i % 3 == 0]
	rb = [i for i in range(1, N + 1) if i % 3 != 0]
	for i in range(N):
		if col[i] == 0:
			Ans[i] = zb.pop()
	rb += zb
	for i in range(N):
		if col[i] == 1:
			Ans[i] = rb.pop()
elif one <= black and two <= white:
	zb = [i for i in range(1, N + 1) if i % 3 == 0]
	ob = [i for i in range(1, N + 1) if i % 3 == 1]
	tb = [i for i in range(1, N + 1) if i % 3 == 2]
	for i in range(N):
		if col[i] == 1:
			if ob:
				Ans[i] = ob.pop()
			else:
				Ans[i] = zb.pop()
		elif tb:
			Ans[i] = tb.pop()
		else:
			Ans[i] = zb.pop()
else:
	assert False, ''
print(*Ans)


from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
N = int(input())
AB = [list(map(int, input().split())) for i in range(N - 1)]
data = [[] for i in range(N + 1)]
for (a, b) in AB:
	data[a].append(b)
	data[b].append(a)
lst = [0 for i in range(N + 1)]
stack = deque([[1, 0]])
visited = set([1])
while stack:
	(a, m) = stack.popleft()
	for p in data[a]:
		if not p in visited:
			visited.add(p)
			stack.append([p, m + 1])
			lst[p] = m + 1
oddslst = [i for i in range(len(lst)) if i and (not lst[i] % 2)]
evenlst = [i for i in range(len(lst)) if i and lst[i] % 2]
lst = [0 for i in range(N + 1)]
if N // 3 < len(oddslst) and N // 3 < len(evenlst):
	for i in range(1, N + 1):
		if i % 3 == 1:
			lst[oddslst.pop()] = i
		if i % 3 == 2:
			lst[evenlst.pop()] = i
	oddslst += evenlst
	for i in range(1, N + 1):
		if i % 3 == 0:
			lst[oddslst.pop()] = i
else:
	if len(evenlst) < len(oddslst):
		(oddslst, evenlst) = (evenlst, oddslst)
	for i in range(1, N + 1):
		if i % 3 == 0:
			if oddslst:
				lst[oddslst.pop()] = i
			else:
				lst[evenlst.pop()] = i
		else:
			lst[evenlst.pop()] = i
print(' '.join([str(i) for i in lst if i]))


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
E = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, readline().split())
	E[a].append(b)
	E[b].append(a)
DIST = [-1] * (N + 1)
STACK = [1]
DIST[1] = 0
COLOR = [None] * (N + 1)

def setColor(v, c):
	COLOR[v] = c
	for w in E[v]:
		if COLOR[w] == None:
			setColor(w, -c)
setColor(1, 1)
EVEN = [i for (i, x) in enumerate(COLOR) if x == 1 and i > 0]
ODD = [i for (i, x) in enumerate(COLOR) if x == -1 and i > 0]
listN = list(range(1, N + 1))
mod1 = deque(listN[0::3])
mod2 = deque(listN[1::3])
mod0 = deque(listN[2::3])
ANS = [-1] * (N + 1)

def assign(target, arr1, arr2=[], arr3=[]):
	source = [arr1, arr2, arr3]
	idx = 0
	for e in target:
		if len(source[idx]) == 0:
			idx += 1
		ANS[e] = source[idx].pop()
	return 0
if len(EVEN) <= len(mod0):
	assign(EVEN, mod0)
	assign(ODD, mod0, mod1, mod2)
elif len(ODD) <= len(mod0):
	assign(ODD, mod0)
	assign(EVEN, mod0, mod1, mod2)
else:
	assign(EVEN, mod1, mod0)
	assign(ODD, mod2, mod0)
ANS = ANS[1:]
print(' '.join(map(str, ANS)))


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v, step):
	global node0, node1
	if step & 1:
		color[v] = 1
		node1 += 1
	else:
		color[v] = 0
		node0 += 1
	for nv in edge[v]:
		if color[nv] is None:
			dfs(nv, step + 1)
N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
	(a, b) = map(int, s.split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)
ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
if node0 > num0 and node1 > num0:
	cur = 0
	while num1 > 0:
		if color[cur] == 1:
			ans[cur] = 3 * num1 - 2
			num1 -= 1
		cur += 1
	cur = 0
	while num2 > 0:
		if color[cur] == 0:
			ans[cur] = 3 * num2 - 1
			num2 -= 1
		cur += 1
elif node0 <= num0:
	cur = 0
	while node0 > 0:
		if color[cur] == 0:
			ans[cur] = 3 * num0
			num0 -= 1
			node0 -= 1
		cur += 1
else:
	cur = 0
	while node1 > 0:
		if color[cur] == 1:
			ans[cur] = 3 * num0
			num0 -= 1
			node1 -= 1
		cur += 1
cur = 0
while num0 > 0:
	if ans[cur] is None:
		ans[cur] = 3 * num0
		num0 -= 1
	cur += 1
while num1 > 0:
	if ans[cur] is None:
		ans[cur] = 3 * num1 - 2
		num1 -= 1
	cur += 1
while num2 > 0:
	if ans[cur] is None:
		ans[cur] = 3 * num2 - 1
		num2 -= 1
	cur += 1
print(*ans)


(n, *L) = map(int, open(0).read().split())
g = [[] for _ in range(n)]
for (a, b) in zip(*[iter(L)] * 2):
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
tr = [-1] * n
q = [0]
tr[0] = 0
while q:
	cu = q.pop()
	for nx in g[cu]:
		if tr[nx] < 0:
			tr[nx] = 1 - tr[cu]
			q.append(nx)
lab = [-1] * n
(z, o) = map(tr.count, (0, 1))
if z <= n // 3 or o <= n // 3:
	f = 0 if z <= n // 3 else 1
	onetwo = 1
	thr = 3
	for (i, x) in enumerate(tr):
		if x == f:
			lab[i] = thr
			thr += 3
	for (i, x) in enumerate(tr):
		if x == 1 - f:
			if thr <= n:
				lab[i] = thr
				thr += 3
			else:
				lab[i] = onetwo
				onetwo += 1 if onetwo % 3 == 1 else 2
else:
	one = 1
	for (i, x) in enumerate(tr):
		if x == 0:
			lab[i] = one
			one += 3
			if one > n:
				break
	two = 2
	for (i, x) in enumerate(tr):
		if x == 1:
			lab[i] = two
			two += 3
			if two > n:
				break
	thr = 3
	for i in range(n):
		if lab[i] < 0:
			lab[i] = thr
			thr += 3
print(*lab)


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

def dfs(v, step):
	global node0, node1
	if step & 1:
		color[v] = 1
		node1 += 1
	else:
		color[v] = 0
		node0 += 1
	for nv in edge[v]:
		if color[nv] is None:
			dfs(nv, step + 1)
N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
	(a, b) = map(int, s.split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)
ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
q0 = deque()
q1 = deque()
q = deque()
if node0 > num0 and node1 > num0:
	for i in range(1, num0 + 1):
		q.append(3 * i)
	for i in range(1, num1 + 1):
		q1.append(3 * i - 2)
	for i in range(1, num2 + 1):
		q0.append(3 * i - 1)
elif node0 <= num0:
	for i in range(1, node0 + 1):
		q0.append(3 * i)
	for i in range(node0 + 1, num0 + 1):
		q.append(3 * i)
	for i in range(1, num1 + 1):
		q1.append(3 * i - 2)
	for i in range(1, num2 + 1):
		q.append(3 * i - 1)
else:
	for i in range(1, node1 + 1):
		q1.append(3 * i)
	for i in range(node1 + 1, num0 + 1):
		q.append(3 * i)
	for i in range(1, num1 + 1):
		q.append(3 * i - 2)
	for i in range(1, num2 + 1):
		q0.append(3 * i - 1)
for i in range(N):
	if color[i] == 0:
		Q = q0 if q0 else q
		ans[i] = Q.pop()
	else:
		Q = q1 if q1 else q
		ans[i] = Q.pop()
print(*ans)


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, -1, 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(odd) <= 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)


import sys
sys.setrecursionlimit(4100000)
import math
import logging
logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)
from collections import defaultdict

def resolve():
	global N, neighbor_list, color_list, count_dict
	N = [int(x) for x in sys.stdin.readline().split()][0]
	neighbor_list = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = sys.stdin.readline().split()
		a = int(a) - 1
		b = int(b) - 1
		neighbor_list[a].append(b)
		neighbor_list[b].append(a)
	logger.debug('{}'.format([]))
	color_list = [None for _ in range(N)]
	count_dict = defaultdict(int)
	dfs(0, 0)
	q0_list = list(range(3, N + 1, 3))
	q1_list = list(range(1, N + 1, 3))
	q2_list = list(range(2, N + 1, 3))
	ret_list = [0 for _ in range(N)]
	if count_dict[0] > N // 3 and count_dict[1] > N // 3:
		i_q0 = i_q1 = i_q2 = 0
		for (i, c) in enumerate(color_list):
			if c == 0:
				if i_q1 < len(q1_list):
					ret_list[i] = q1_list[i_q1]
					i_q1 += 1
				else:
					ret_list[i] = q0_list[i_q0]
					i_q0 += 1
			elif i_q2 < len(q2_list):
				ret_list[i] = q2_list[i_q2]
				i_q2 += 1
			else:
				ret_list[i] = q0_list[i_q0]
				i_q0 += 1
		print(' '.join([str(c) for c in ret_list]))
		return
	if count_dict[0] <= N // 3:
		i_q0 = i_q1 = i_q2 = 0
		for (i, c) in enumerate(color_list):
			if c == 0:
				ret_list[i] = q0_list[i_q0]
				i_q0 += 1
		for (i, c) in enumerate(color_list):
			if c == 1:
				if i_q0 < len(q0_list):
					ret_list[i] = q0_list[i_q0]
					i_q0 += 1
				elif i_q1 < len(q1_list):
					ret_list[i] = q1_list[i_q1]
					i_q1 += 1
				else:
					ret_list[i] = q2_list[i_q2]
					i_q2 += 1
		print(' '.join([str(c) for c in ret_list]))
		return
	if count_dict[1] <= N // 3:
		i_q0 = i_q1 = i_q2 = 0
		for (i, c) in enumerate(color_list):
			if c == 1:
				ret_list[i] = q0_list[i_q0]
				i_q0 += 1
		for (i, c) in enumerate(color_list):
			if c == 0:
				if i_q0 < len(q0_list):
					ret_list[i] = q0_list[i_q0]
					i_q0 += 1
				elif i_q1 < len(q1_list):
					ret_list[i] = q1_list[i_q1]
					i_q1 += 1
				else:
					ret_list[i] = q2_list[i_q2]
					i_q2 += 1
		print(' '.join([str(c) for c in ret_list]))
		return

def dfs(i, color):
	global N, neighbor_list, color_list, count_dict
	color_list[i] = color
	count_dict[color] += 1
	for i_next in neighbor_list[i]:
		if color_list[i_next] is None:
			dfs(i_next, not color)
resolve()
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):

	def assertIO(self, input, output):
		(stdout, stdin) = (sys.stdout, sys.stdin)
		(sys.stdout, sys.stdin) = (StringIO(), StringIO(input))
		resolve()
		sys.stdout.seek(0)
		out = sys.stdout.read()[:-1]
		(sys.stdout, sys.stdin) = (stdout, stdin)
		self.assertEqual(out, output)

	def test_入力例_1(self):
		input = '5\n1 2\n1 3\n3 4\n3 5'
		output = '1 2 5 4 3'
		self.assertIO(input, output)


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

def run(cur, tr, dist, d=1, pre=-1, recur=1, save_recur=[]):
	for node in tr[cur]:
		if node == pre:
			continue
		dist[d].append(node)
		if recur > 500:
			dic_ = {'cur': node, 'tr': tr, 'dist': dist, 'd': (d + 1) % 2, 'pre': cur, 'recur': recur + 1}
			save_recur.append(dic_)
			return None
		run(node, tr, dist, (d + 1) % 2, pre=cur, recur=recur + 1, save_recur=save_recur)
	return None
tr = {}
for line in ab:
	if line[0] not in tr.keys():
		tr[line[0]] = [line[1]]
	else:
		tr[line[0]].append(line[1])
	if line[1] not in tr.keys():
		tr[line[1]] = [line[0]]
	else:
		tr[line[1]].append(line[0])
dist = {0: [1], 1: []}
save_rec = []
run(1, tr, dist, save_recur=save_rec)
while True:
	save_rec2 = save_rec
	save_rec = []
	for dict in save_rec2:
		run(dict['cur'], dict['tr'], dict['dist'], dict['d'], dict['pre'], dict['recur'], save_recur=save_rec)
	if save_rec == []:
		break
perm = [0] * (N + 1)
(rem1_max, rem2_max, rem0_max) = (int(N / 3), int(N / 3), int(N / 3))
if N % 3 == 1:
	rem1_max += 1
if N % 3 == 2:
	rem1_max += 1
	rem2_max += 1
if (len(dist[0]) <= N / 3) | (len(dist[0]) >= 2 * N / 3):
	bool = int(len(dist[0]) <= N / 3)
	h0 = 1
	for k in dist[1 - bool]:
		perm[k] = 3 * h0
		h0 += 1
	nums = [3 * i for i in range(h0, rem0_max + 1)] + [3 * i + 1 for i in range(0, rem1_max)] + [3 * i + 2 for i in range(0, rem2_max)]
	for (k, val) in zip(dist[bool], nums):
		perm[k] = val
else:
	n = int(N / 3)
	if N % 3 == 2:
		n += 1
	h1 = 0
	h2 = 0
	idx = 0
	bool = int(len(dist[0]) > len(dist[1]))
	for alpha in range(n):
		even = dist[bool][idx]
		perm[even] = alpha * 3 + 1
		odd = dist[1 - bool][idx]
		perm[odd] = alpha * 3 + 2
		idx += 1
	h0 = 1
	for k in dist[1 - bool][idx:]:
		perm[k] = 3 * h0
		h0 += 1
	nums = [3 * i for i in range(h0, rem0_max + 1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]
	for (h, k) in enumerate(dist[bool][idx:]):
		perm[k] = nums[h]
print(' '.join(list(map(str, perm[1:]))))


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()
		elif len(a) != 0:
			ans[i - 1] = a.pop()
		elif len(b) != 0:
			ans[i - 1] = b.pop()
		else:
			ans[i - 1] = c.pop()
elif N - x <= N // 3:
	for i in range(1, N + 1):
		if r[i] == 0:
			ans[i - 1] = c.pop()
		elif len(a) != 0:
			ans[i - 1] = a.pop()
		elif len(b) != 0:
			ans[i - 1] = b.pop()
		else:
			ans[i - 1] = c.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()
		elif 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)))


import sys
input = sys.stdin.readline
n = int(input())
edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
used = [0] * n
tank = [0]
used[0] = 1
ca = 0
cb = 0
while tank:
	p = tank.pop()
	if used[p] > 0:
		ca += 1
	for e in edge[p]:
		if used[e] == 0:
			used[e] = -used[p]
			tank.append(e)
cb = n - ca
res = [0] * n
flag = [True] * (n + 2)
if ca <= n // 3:
	tmp = 0
	for i in range(n):
		if used[i] == 1:
			tmp += 3
			res[i] = tmp
			flag[tmp] = False
	tmp = 1
	for i in range(n):
		if used[i] != 1:
			res[i] = tmp
			flag[tmp] = False
			while not flag[tmp]:
				tmp += 1
	print(*res)
elif cb <= n // 3:
	tmp = 0
	for i in range(n):
		if used[i] == -1:
			tmp += 3
			res[i] = tmp
			flag[tmp] = False
	tmp = 1
	for i in range(n):
		if used[i] != -1:
			res[i] = tmp
			flag[tmp] = False
			while not flag[tmp]:
				tmp += 1
	print(*res)
else:
	tmp = -2
	for i in range(n):
		if used[i] == -1:
			tmp += 3
			if tmp > n:
				tmp = 3
			res[i] = tmp
			flag[tmp] = False
	tmp = 2
	for i in range(n):
		if used[i] != -1:
			res[i] = tmp
			flag[tmp] = False
			while not flag[tmp]:
				tmp += 1
				if tmp > n:
					tmp = 3
					break
	print(*res)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
sys.setrecursionlimit(10 ** 9)
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
flag = [0] * n

def dfs(cur, par, f):
	flag[cur] = f
	for to in G[cur]:
		if to != par:
			dfs(to, cur, f ^ 1)
dfs(0, -1, 0)
a = sum(flag)
b = n - a
one = []
two = []
three = []
for i in range(1, n + 1):
	if i % 3 == 0:
		three.append(i)
	elif i % 3 == 1:
		one.append(i)
	else:
		two.append(i)
k = n // 3
ans = [0] * n
if k < a and k < b:
	for i in range(n):
		if flag[i]:
			if one:
				ans[i] = one.pop()
			else:
				ans[i] = three.pop()
		elif two:
			ans[i] = two.pop()
		else:
			ans[i] = three.pop()
elif k >= a:
	for i in range(n):
		if flag[i]:
			ans[i] = three.pop()
	res = one + two + three
	for i in range(n):
		if not flag[i]:
			ans[i] = res.pop()
else:
	for i in range(n):
		if not flag[i]:
			ans[i] = three.pop()
	res = one + two + three
	for i in range(n):
		if flag[i]:
			ans[i] = res.pop()
print(*ans)


n = int(input())
edge = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
ans = [0 for i in range(n + 1)]
od = [1]
ev = []
q = [1]
c = [1 for i in range(n + 1)]
c[1] = 0
t = 0
while q:
	tl = q[:]
	q = []
	for i in tl:
		for j in edge[i]:
			if c[j]:
				q.append(j)
				c[j] = 0
				if t:
					od.append(j)
				else:
					ev.append(j)
	t ^= 1
if len(od) > len(ev):
	(od, ev) = (ev, od)
if len(od) <= n // 3:
	t = 3
	for i in od:
		ans[i] = t
		t += 3
	x = 0
	for (i, j) in enumerate(ans):
		if j == 0:
			ans[i] = x
			x += 1
			if x % 3 == 0 and x < t:
				x += 1
else:
	t = 0
	for i in range(1, n + 1, 3):
		ans[ev[t]] = i
		t += 1
	t = 0
	for i in range(2, n + 1, 3):
		ans[od[t]] = i
		t += 1
	t = 0
	for (i, j) in enumerate(ans):
		if j == 0:
			ans[i] = t
			t += 3
print(' '.join(map(str, ans[1:])))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import deque
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
color = [-1] * n

def dfs(p, v, c):
	for nv in edge[v]:
		color[nv] = not c
		if nv == p:
			continue
		dfs(v, nv, not c)
dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
	(white, black) = (black, white)
	color = [not item for item in color]
if white <= n // 3:
	threes = [item for item in range(1, n + 1) if item % 3 == 0]
	others = [item for item in range(1, n + 1) if item % 3 != 0]
	array = deque(others + threes)
else:
	threes = [item for item in range(1, n + 1) if item % 3 == 0]
	twos = [item for item in range(1, n + 1) if item % 3 == 2]
	ones = [item for item in range(1, n + 1) if item % 3 == 1]
	array = deque(ones + threes + twos)
ans = [-1] * n
for (i, is_white) in enumerate(color):
	if is_white:
		ans[i] = array.pop()
	else:
		ans[i] = array.popleft()
print(*ans)


import sys
from collections import deque

def solve():
	input = sys.stdin.readline
	N = int(input())
	Edge = [[] for _ in range(N)]
	Par = [0 for _ in range(N)]
	Son = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		Edge[a - 1].append(b - 1)
		Edge[b - 1].append(a - 1)
	Dist = [0] * N
	DistType = [0, 0]
	q = deque()
	q.append((0, 0, 0))
	modCount = [N // 3, N // 3, N // 3]
	if N % 3 == 1:
		modCount[1] += 1
	elif N % 3 == 2:
		modCount[1] += 1
		modCount[2] += 1
	modIndex = [0, 0, 0]
	search = deque()
	while q:
		(nowNode, preNode, dist) = q.popleft()
		Dist[nowNode] = dist
		Par[nowNode] = preNode
		Son[preNode].append(nowNode)
		search.append(nowNode)
		DistType[dist % 2] += 1
		for nextNode in Edge[nowNode]:
			if nextNode != preNode:
				q.append((nextNode, nowNode, dist + 1))
	Ans = [-1] * N
	if DistType[0] <= modCount[0]:
		for (i, d) in enumerate(Dist):
			if d % 2 == 0:
				Ans[i] = 3 * modIndex[0] + 3
				modIndex[0] += 1
			elif modIndex[1] < modCount[1]:
				Ans[i] = 3 * modIndex[1] + 1
				modIndex[1] += 1
			elif modIndex[2] < modCount[2]:
				Ans[i] = 3 * modIndex[2] + 2
				modIndex[2] += 1
			else:
				Ans[i] = 3 * modIndex[0] + 3
				modIndex[0] += 1
	elif DistType[1] <= modCount[0]:
		for (i, d) in enumerate(Dist):
			if d % 2 == 1:
				Ans[i] = 3 * modIndex[0] + 3
				modIndex[0] += 1
			elif modIndex[1] < modCount[1]:
				Ans[i] = 3 * modIndex[1] + 1
				modIndex[1] += 1
			elif modIndex[2] < modCount[2]:
				Ans[i] = 3 * modIndex[2] + 2
				modIndex[2] += 1
			else:
				Ans[i] = 3 * modIndex[0] + 3
				modIndex[0] += 1
	else:
		for (i, d) in enumerate(Dist):
			if d % 2 == 0:
				if modIndex[1] < modCount[1]:
					Ans[i] = 3 * modIndex[1] + 1
					modIndex[1] += 1
				else:
					Ans[i] = 3 * modIndex[0] + 3
					modIndex[0] += 1
			elif modIndex[2] < modCount[2]:
				Ans[i] = 3 * modIndex[2] + 2
				modIndex[2] += 1
			else:
				Ans[i] = 3 * modIndex[0] + 3
				modIndex[0] += 1
	print(' '.join(map(str, Ans)))
	return 0
solve()