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 defaultdict,deque,Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a-= 1 ; b-=1
    lines[a].add(b)
    lines[b].add(a)


depths = [set() for _ in range(N)]
Ev = 0
Od = 0

def dfs(s,b,d):
    global depths
    global Ev
    global Od
    depths[d].add(s)

    if d%2 == 0:
        Ev += 1
    else:
        Od += 1

    for t in lines[s]:
        if t == b:
            continue
        else:
            dfs(t,s,d+1)


dfs(0,-1,0)

# print(depths)

n1 = (N+2)//3
n2 = (N+1)//3
n0 = (N+0)//3

# print(n0,n1,n2)
ansl = [-1]*N


if Ev <= n0 or Od <= n0:
    if Ev <= n0: fl = 0
    else: fl = 1

    for d, ps in enumerate(depths):
        if d%2 == fl:
            for p in ps:
                ansl[p] = n0*3
                n0 -= 1
        else:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                elif n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
else:
    for d, ps in enumerate(depths):
        if d%2 == 0:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
        else:
            for p in ps:
                if n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1

print(" ".join(map(str,ansl)))