Problem: 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

Solution (in PYTHON3):

Solution:
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 # uからの距離の初期化
    d[u] = 0 # 自分との距離は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)