# Original solution
n = int(eval(input()))
lst = [[] for i in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    lst[ai].append(bi)
    lst[bi].append(ai)

tf = [0 for i in range(n+1)]
tf[1] = 1
iro = 1
queue = lst[1]
while queue != []:
    iro = -iro
    new_queue = []
    for i in queue:
        if tf[i] == 0:
            tf[i] = iro
            for j in lst[i]:
                if tf[j] == 0:
                    new_queue.append(j)
    queue = new_queue

n_minus = tf.count(-1)
n_plus = tf.count(1)
ans = [0 for i in range(n)]

if n_minus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

elif n_plus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

else:
    bai = 1
    kouho1 = 1
    kouho2 = 2
    for i in range(1, n+1):
        if tf[i] == 1:
            if kouho1 <= n:
                ans[i-1] = kouho1
                kouho1 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1
        else:
            if kouho2 <= n:
                ans[i-1] = kouho2
                kouho2 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1

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

# Optimized solution
n = int(eval(input()))
lst = [[] for i in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    lst[ai].append(bi)
    lst[bi].append(ai)

tf = [0 for i in range(n+1)]
tf[1] = 1
iro = 1
queue = lst[1]
while queue != []:
    iro = -iro
    new_queue = []
    for i in queue:
        tf[i] = iro
        for j in lst[i]:
            if tf[j] == 0:
                new_queue.append(j)
    queue = new_queue

n_minus = tf.count(-1)
n_plus = tf.count(1)
ans = [0 for i in range(n)]

if n_minus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

elif n_plus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

else:
    bai = 1
    kouho1 = 1
    kouho2 = 2
    for i in range(1, n+1):
        if tf[i] == 1:
            if kouho1 <= n:
                ans[i-1] = kouho1
                kouho1 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1
        else:
            if kouho2 <= n:
                ans[i-1] = kouho2
                kouho2 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1

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