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 queue

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n-1)]
num_0_mod_3 = n // 3
num_2_mod_3 = (n+1) // 3
num_1_mod_3 = (n+2) // 3


def add_edge(u, v ):
    G[u].append(v)
    G[v].append(u)

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
    add_edge(edge[0]-1, edge[1]-1)

num_distance_even = 0
num_distance_odd = 0

q = queue.Queue()
q.put(0)

distance = [-1] * n
distance[0] = 0
num_distance_even += 1

for v in G[0]:
    q.put(v)

while(q.qsize() > 0):
    now = q.get()
    for v in G[now]:
        if distance[v] >= 0:
            pass
        else:
            q.put(v)
            distance[v] = distance[now] + 1
            if (distance[v] & 1):
                num_distance_odd += 1
            else:
                num_distance_even += 1

# print(distance)
# print(num_distance_even, num_distance_odd)

ans = [-1] * n

index_one = 1
index_two = 2
index_zero = 3

if num_distance_even >= num_1_mod_3 + num_2_mod_3:
    # evenに120 oddに0

    for i in range(n):
        if (distance[i] & 1) == 1:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
    # evenに0 oddに012
    for i in range(n):
        if (distance[i] & 1) == 0:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


else:
#     num_distance_even <= num_distance_odd * 2 and num_distance_odd <= num_distance_even * 2:
    # evenを2、oddを1、適宜0
    for i in range(n):
        if (distance[i] & 1) == 1:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            else:
                ans[i] = index_zero
                index_zero += 3
        else:
            if (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


print(' '.join(list(map(str, ans))))