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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if n < 4:
        print(*range(1,n+1),sep = " ")
        return
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]^1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    n1 = sum(d)
    n0 = len(d)-n1
    if n1 > n0:
        for i in range(n):
            d[i] ^= 1
        n0,n1 = n1,n0
    p = [(n+2)//3, (n+1)//3, n//3]
    k = [1,2,3]
    ans = [0]*n
    if n1 >= p[1]:
        for i in range(n):
            di = d[i]
            if not p[di]:
                di = 2
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    else:
        for i in range(n):
            di = d[i]
            if di == 1:
                di = 2
            while not p[di]:
                di += 1
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()