from collections import deque
n = int(input())
mod_list = [0]*n
mod_list[0] = 1
tree = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append([a-1, b-1])
    tree[b-1].append([b-1, a-1])

already = [False]*n
not_yet = deque(tree[0])
judge = [False]*n

already[0] = True
flag = True
key = 0
count = 0
c0, c1, c2 = 0, 1, 0
while not_yet:
    key = not_yet[0]
    not_yet.popleft()
    p, q = key[0], key[1]
    if key == p:
        count += 1
        if count >= 3:
            judge[q] = True
    else:
        key = p
        count = 1
    already[q] = True
    mod_list[q] = mod_list[p]+1
    mod_list[q] %= 2
    if judge[q]:
        c0 += 1
    elif mod_list[q]:
        c1 += 1
    else:
        c2 += 1
    
    for value in tree[q]:
        if already[value[1]]:
            continue
        else:
            not_yet.append(value)

ans = [0]*n
mod_0 = [int(x) for x in range(3, n+1, 3)]
mod_1 = [int(x) for x in range(1, n+1, 3)]
mod_2 = [int(x) for x in range(2, n+1, 3)]

if c1 < c2:
    mod_1, mod_2 = mod_2, mod_1

k0, k1, k2 = 0, 0, 0
for i in range(n):
    if judge[i]:
        ans[i] = mod_0[k0]
        k0 += 1
        continue
    if mod_list[i] == 1:
        if k1 == len(mod_1):
            ans[i] = mod_0[k0]
            k0 += 1
            continue
        ans[i] = mod_1[k1]
        k1 += 1
        continue
    else:
        if k2 == len(mod_2):
            ans[i] = mod_0[k0]
            k0 += 1
            continue
        ans[i] = mod_2[k2]
        k2 += 1
        continue
print(*ans)

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    dist = [0]*n

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            



    
if __name__ == "__main__":
    main()