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 = 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:])