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 bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(point, pre):
        p = lis[point]
        for nex in edg[point]:
            if nex == pre:
                continue
            lis[nex] = p + 1
            f(nex, point)
        return
    n = II()
    ab = LIR_(n - 1)
    lis = [-1] * n
    edg = [[] for _ in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    lis[0] = 1
    f(0, -1)
    d = [0, 0]
    for i in lis:
        d[i & 1] += 1
    ans = [None] * n
    if d[0] <= n // 3:
        t = 1
        for i in range(n):
            if lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    elif d[1] <= n // 3:
        t = 1
        for i in range(n):
            if not lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    else:
        t = n // 3
        odd = 1
        even = 2
        for i in range(n):
            if t:
                if lis[i] & 1:
                    if d[1] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(odd)
                        odd += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[1] -= 1
                else:
                    if d[0] <= n // 3 + (n % 3 >= 2):
                        ans[i] = str(even)
                        even += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[0] -= 1 
            else:
                if lis[i] & 1:
                    ans[i] = str(odd)
                    odd += 3
                else:
                    ans[i] = str(even)
                    even += 3
    print(" ".join(ans))


    return


#main
if __name__ == '__main__':
    solve()