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())
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)