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

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()
    #print(cc)
    #print(cntc)
    m1=(n-1)//3+1
    m2=(n-2)//3+1
    m3=n//3
    #print(m1,m2,m3)
    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:
        #mncの色に3の倍数、あと自由
        for u in range(n):
            if cc[u]==mnc:ans[u]=p3.pop()
            else:
                if 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:
        #多い方にm1、少ない方にm2を振って、残りをm3で埋める
        for u in range(n):
            if cc[u]==mnc:
                if p2:ans[u]=p2.pop()
                else:ans[u]=p3.pop()
            else:
                if p1:ans[u]=p1.pop()
                else:ans[u]=p3.pop()
    print(*ans)

main()