import sys

import numpy as np

from collections import Counter



sr = lambda: sys.stdin.readline().rstrip()

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



# 1 mod 3のグループを先に決めてあとは順番に



N = ir()

graph = [[] for _ in range(N+1)] # 1-indexed

for _ in range(N-1):

    a, b = lr()

    graph[a].append(b)

    graph[b].append(a)



root = 1

rank = [0] * (N+1) # 1-indexed

rank[1] = 1

parent = [0] * (N+1) # 1-indexed

order = []

stack = [root]

while stack:

    cur = stack.pop()

    r = rank[cur]

    order.append(cur)

    for next in graph[cur]:

        if next == parent[cur]:

            continue

        parent[next] = cur

        rank[next] = r + 1

        stack.append(next)



counter = [0, 0]

for x in rank[1:]:

    counter[x%2] += 1

num0mod3 = N // 2

num1mod3 = (N+2) // 3

num2mod3 = (N+1) // 3

answer = [0] * (N+1)

if max(counter) >= num1mod3 + num2mod3:

    #この時ここに1mod3、2mod3を全部入れる

    if counter[0] > counter[1]:

        index = 0

    else:

        index = 1

    cur = 1

    used = set()

    for i in range(1, N+1):

        if rank[i] % 2 == index:

            answer[i] = cur

            used.add(cur)

            cur += 1

            if cur % 3 == 0:

                cur += 1

            if cur > N:

                break

    cur = 1

    for j in range(1, N+1):

        while cur in used:

            cur += 1

        if answer[j] == 0:

            answer[j] = cur

            used.add(cur)

else:

    #ここではcounterの多い方にnum1mod3を入れる

    if counter[0] > counter[1]:

        index = 0

    else:

        index = 1

    cur = 1

    used = set()

    for i in range(1, N+1):

        if rank[i] % 2 == index:

            answer[i] = cur

            used.add(cur)

            cur += 3

            if cur > N:

                break

    cur = 2

    for i in range(1, N+1):

        if rank[i] % 2 == 1-index:

            answer[i] = cur

            used.add(cur)

            cur += 3

            if cur > N:

                break

    cur = 1

    for j in range(1, N+1):

        while cur in used:

            cur += 1

        if answer[j] == 0:

            answer[j] = cur

            used.add(cur)



print((*answer[1:]))

import sys



sr = lambda: sys.stdin.readline().rstrip()

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



# 1(mod 3)のグループと2(mod 3)を先に決める

N = ir()

graph = [[] for _ in range(N+1)] # 1-indexed

for _ in range(N-1):

    a, b = lr()

    graph[a].append(b)

    graph[b].append(a)



root = 1

rank = [0] * (N+1) # 1-indexed

rank[1] = 1

parent = [0] * (N+1) # 1-indexed

stack = [root]

while stack:

    cur = stack.pop()

    r = rank[cur]

    for next in graph[cur]:

        if next == parent[cur]:

            continue

        parent[next] = cur

        rank[next] = r + 1

        stack.append(next)



counter = [0, 0]

for x in rank[1:]:

    counter[x%2] += 1

num0mod3 = N // 2

num1mod3 = (N+2) // 3

num2mod3 = (N+1) // 3

answer = [0] * (N+1)

if max(counter) >= num1mod3 + num2mod3:

    #この時ここに1mod3、2mod3を全部入れる

    if counter[0] > counter[1]:

        index = 0

    else:

        index = 1

    cur = 1

    used = set()

    for i in range(1, N+1):

        if rank[i] % 2 == index:

            answer[i] = cur

            used.add(cur)

            cur += 1

            if cur % 3 == 0:

                cur += 1

            if cur > N:

                break

    cur = 1

    for j in range(1, N+1):

        while cur in used:

            cur += 1

        if answer[j] == 0:

            answer[j] = cur

            used.add(cur)

else:

    #ここではcounterの多い方にnum1mod3を入れる

    if counter[0] > counter[1]:

        index = 0

    else:

        index = 1

    cur = 1

    used = set()

    for i in range(1, N+1):

        if rank[i] % 2 == index:

            answer[i] = cur

            used.add(cur)

            cur += 3

            if cur > N:

                break

    cur = 2

    for i in range(1, N+1):

        if rank[i] % 2 == 1-index:

            answer[i] = cur

            used.add(cur)

            cur += 3

            if cur > N:

                break

    cur = 1

    for j in range(1, N+1):

        while cur in used:

            cur += 1

        if answer[j] == 0:

            answer[j] = cur

            used.add(cur)



print((*answer[1:]))

import sys
import numpy as np
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# 1 mod 3のグループを先に決めてあとは順番に
N = ir()
graph = [[] for _ in range(N + 1)]  # 1-indexed
for _ in range(N - 1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)
root = 1
rank = [0] * (N + 1)  # 1-indexed
rank[1] = 1
parent = [0] * (N + 1)  # 1-indexed
order = []
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)
counter = [0, 0]
for x in rank[1:]:
    counter[x % 2] += 1
num0mod3 = N // 2
num1mod3 = (N + 2) // 3
num2mod3 = (N + 1) // 3
answer = [0] * (N + 1)
if max(counter) >= num1mod3 + num2mod3:
    # この時ここに1mod3、2mod3を全部入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N + 1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N + 1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    # ここではcounterの多い方にnum1mod3を入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N + 1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N + 1):
        if rank[i] % 2 == 1 - index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N + 1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
print((*answer[1:]))

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# 1(mod 3)のグループと2(mod 3)を先に決める
N = ir()
graph = [[] for _ in range(N + 1)]  # 1-indexed
for _ in range(N - 1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)
root = 1
rank = [0] * (N + 1)  # 1-indexed
rank[1] = 1
parent = [0] * (N + 1)  # 1-indexed
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)
counter = [0, 0]
for x in rank[1:]:
    counter[x % 2] += 1
num0mod3 = N // 2
num1mod3 = (N + 2) // 3
num2mod3 = (N + 1) // 3
answer = [0] * (N + 1)
if max(counter) >= num1mod3 + num2mod3:
    # この時ここに1mod3、2mod3を全部入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N + 1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N + 1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    # ここではcounterの多い方にnum1mod3を入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N + 1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N + 1):
        if rank[i] % 2 == 1 - index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N + 1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
print((*answer[1:]))

-import numpy as np -from collections import Counter -# 1 mod 3のグループを先に決めてあとは順番に +# 1(mod 3)のグループと2(mod 3)を先に決める -order = [] -    order.append(cur)