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:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
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)))