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:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    T = {i: set() for i in range(1, n+1)}
    for ab in map(str.split, args[1:]):
        a, b = map(int, ab)
        T[a].add(b)
        T[b].add(a)

    R = set()
    B = set()

    stack = [(1, 0)]
    while stack:
        i, d = stack.pop()
        if i in R or i in B:
            continue
        if d % 2:
            R.add(i)
        else:
            B.add(i)
        for j in T[i]:
            stack.append((j, d+1))

    R, B = (R, B) if len(R) < len(B) else (B, R)

    ret = [0]*(n+1)
    if len(R) <= n//3:
        for i in range(1, n+1):
            if i % 3:
                ret[B.pop()] = i
            else:
                ret[R.pop() if R else B.pop()] = i
    else:
        for i in range(1, n+1, 3):
            ret[R.pop()] = i
        for i in range(2, n+1, 3):
            ret[B.pop()] = i
        for i in range(3, n+1, 3):
            ret[R.pop() if R else B.pop()] = i

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))