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 math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))


n = int(input())
es = []
nb = [[] for i in range(n)]

for i in range(n-1):
    aa,bb = list(map(int, input().split()))
    a,b = aa-1,bb-1
    nb[a].append(b)
    nb[b].append(a)
#print(nb)

side = [[],[]]
checked = [-1 for i in range(n)]

queue = [0]
side[0].append(0)
checked[0] = 0
fin = 0

while(True):
    if(len(queue) == fin):
        break
    seeing = queue[fin]
    fin+=1
    
    for j in range(len(nb[seeing])):
        nextval = nb[seeing][j]
        if(checked[nextval]==-1):
            nextside =1 - checked[seeing]
            checked[nextval] = nextside
            side[nextside].append(nextval)
            queue.append(nextval)

#print(side)
nums3 = [n//3,n//3,n//3]

if(n%3 >= 1):
    nums3[0]+=1
if(n%3 == 2):
    nums3[1]+=1

#print(nums3)


ans = [-1 for i in range(n)]

if(len(side[0]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou0):
        ans[side[0][i]] = 3 + 3*i
    for j in range(nums3[2] - cou0):
        ans[side[1][j]] = 3 + 3*(j+cou0)
    startnum = nums3[2] - cou0
    for j in range(cou1 - startnum):
        ans[side[1][startnum+j]] = non3[j]
    
    #print("side0")
    
elif(len(side[1]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou1):
        ans[side[1][i]] = 3 + 3*i
    for j in range(nums3[2] - cou1):
        ans[side[0][j]] = 3 + 3*(j+cou1)
    startnum = nums3[2] - cou1
    for j in range(cou0 - startnum):
        ans[side[0][startnum+j]] = non3[j]
        #print("now",startnum+j,non3[j])

    #print("side1")
else:
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    for i in range(nums3[0]):
        ans[side[0][i]] = 1 + 3*i
        
    for i in range(nums3[1]):
        ans[side[1][i]] = 2 + 3*i
        
    start0 = nums3[0]
    done0 = cou0 - nums3[0]
    start1 = nums3[1]
    done1 = cou1 - nums3[1]
    for i in range(done0):
        ans[side[0][start0 + i]] = 3 + 3 * i
    for i in range(done1):
        ans[side[1][start1 + i]] = 3 + 3 * (i + done0)

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