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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if i % 3 == 0:
            if r:
                ans[r.pop()] = i
            elif b:
                ans[b.pop()] = i
print(*ans)