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 os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths, weights)
    :rtype: (list of int, list of int, list of int)
    """
    seen = [False] * (max_v + 1)
    # 頂点の履歴
    trails = []
    # 深さの履歴
    depths = []
    # 距離の履歴
    weights = []
    # Overflow 回避のためループで
    stack = [(root, 0, 0, True)]
    while stack:
        v, d, w, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        weights.append(w)
        if not forward:
            continue

        for u, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, -w, False))
                stack.append((u, d + 1, w, True))
    return trails, depths, weights


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]

# AB = generate_tree(N)
# plot_graph(AB)
# for a, b in AB:
#     graph[a].append((b, 1))
#     graph[b].append((a, 1))

for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))

counts = [N // 3, (N + 2) // 3, (N + 1) // 3]

# 二部グラフ
vs, _, _ = eulerian_trail(graph, N - 1)
bp = [0] * N
for i, v in enumerate(vs):
    bp[v] = i & 1


ansmod = [-1] * N
if bp.count(0) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
elif bp.count(1) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 1 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
else:
    # 違う方に違うのを割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[1] > 0:
            ansmod[v] = 1
            counts[1] -= 1
        if b == 1 and counts[2] > 0:
            ansmod[v] = 2
            counts[2] -= 1
# 残りに余ってるのを割り当てる
for v in range(N):
    if ansmod[v] < 0:
        for i in range(3):
            if counts[i] > 0:
                ansmod[v] = i
                counts[i] -= 1
                break

ans = []
M = [3, 1, 2]
for a in ansmod:
    ans.append(M[a])
    M[a] += 3
print(*ans)