import sys

from collections import defaultdict as dd

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 6)

N = int(eval(input()))

e = dd(list)

for _ in range(N - 1):

  u, v = list(map(int, input().split()))

  e[u].append(v)

  e[v].append(u)



cl = [0] * (N + 1)

vis = set()

def dfs(x):

  global cl

  global vis

  vis.add(x)

  for y in e[x]:

    if y in vis: continue

    cl[y] = (cl[x] + 1) % 2

    dfs(y)



dfs(1)

bl = cl.count(1)

wh = N - bl

res = [0] * (N + 1)

nm = [[] for _ in range(3)]

for i in range(1, N + 1): nm[i % 3].append(i)

#print(cl)

if bl <= N // 3:

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

    if cl[i]:

      res[i] = nm[0].pop()

    else:

      if len(nm[1]): res[i] = nm[1].pop()

      elif len(nm[2]): res[i] = nm[2].pop()

      else: res[i] = nm[0].pop()

  print((*res[1: ]))

  exit(0)

if wh <= N // 3:

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

    if cl[i] == 0:

      res[i] = nm[0].pop()

    else:

      if len(nm[1]): res[i] = nm[1].pop()

      elif len(nm[2]): res[i] = nm[2].pop()

      else: res[i] = nm[0].pop()

  print((*res[1: ]))

  exit(0)

#print(nm)

#print(cl, nm)

f = 0

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

  if cl[i]:

    if len(nm[1]):

      res[i] = nm[1].pop()

    else:

      res[i] = nm[0].pop()

  else:

    if len(nm[2]):

      res[i] = nm[2].pop()

    else:

      res[i] = nm[0].pop()



print((*res[1: ]))
import sys

input = sys.stdin.readline

N = int(eval(input()))

e = [[] for _ in range(N + 1)]

for _ in range(N - 1):

  u, v = list(map(int, input().split()))

  e[u].append(v)

  e[v].append(u)



a = [1]

b = []

s = [1]

vis = [0] * (N + 1)

table = [-1] * (N + 1)

table[1] = 1

vis[1] = 1

while len(s):

  x = s.pop()

  for y in e[x]:

    if vis[y]: continue

    vis[y] = 1

    table[y] = table[x] ^ 1

    if table[y]: a.append(y)

    else: b.append(y)

    s.append(y)

if len(a) > len(b): a, b = b, a

res = [0] * (N + 1)

if len(a) <= N // 3:

  ss = set([x for x in range(1, N + 1)])

  x = 3

  for y in a:

    res[y] = x

    ss.discard(x)

    x += 3

  ss = list(ss)

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

    if res[i]: continue

    res[i] = ss.pop()

  print((*res[1: ]))

else:

  ss = set([x for x in range(1, N + 1)])

  x = 2

  for y in a:

    res[y] = x

    ss.discard(x)

    x += 3

    if x > N: break

  x = 3

  for y in a:

    if res[y]: continue

    res[y] = x

    ss.discard(x)

    x += 3

  ss = list(ss)

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

    if res[i]: continue

    res[i] = ss.pop()

  print((*res[1: ]))

import sys
from collections import defaultdict as dd

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(eval(input()))
e = dd(list)
for _ in range(N - 1):
    u, v = list(map(int, input().split()))
    e[u].append(v)
    e[v].append(u)
cl = [0] * (N + 1)
vis = set()


def dfs(x):
    global cl
    global vis
    vis.add(x)
    for y in e[x]:
        if y in vis:
            continue
        cl[y] = (cl[x] + 1) % 2
        dfs(y)


dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1):
    nm[i % 3].append(i)
# print(cl)
if bl <= N // 3:
    for i in range(1, N + 1):
        if cl[i]:
            res[i] = nm[0].pop()
        else:
            if len(nm[1]):
                res[i] = nm[1].pop()
            elif len(nm[2]):
                res[i] = nm[2].pop()
            else:
                res[i] = nm[0].pop()
    print((*res[1:]))
    exit(0)
if wh <= N // 3:
    for i in range(1, N + 1):
        if cl[i] == 0:
            res[i] = nm[0].pop()
        else:
            if len(nm[1]):
                res[i] = nm[1].pop()
            elif len(nm[2]):
                res[i] = nm[2].pop()
            else:
                res[i] = nm[0].pop()
    print((*res[1:]))
    exit(0)
# print(nm)
# print(cl, nm)
f = 0
for i in range(1, N + 1):
    if cl[i]:
        if len(nm[1]):
            res[i] = nm[1].pop()
        else:
            res[i] = nm[0].pop()
    else:
        if len(nm[2]):
            res[i] = nm[2].pop()
        else:
            res[i] = nm[0].pop()
print((*res[1:]))

import sys

input = sys.stdin.readline
N = int(eval(input()))
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v = list(map(int, input().split()))
    e[u].append(v)
    e[v].append(u)
a = [1]
b = []
s = [1]
vis = [0] * (N + 1)
table = [-1] * (N + 1)
table[1] = 1
vis[1] = 1
while len(s):
    x = s.pop()
    for y in e[x]:
        if vis[y]:
            continue
        vis[y] = 1
        table[y] = table[x] ^ 1
        if table[y]:
            a.append(y)
        else:
            b.append(y)
        s.append(y)
if len(a) > len(b):
    a, b = b, a
res = [0] * (N + 1)
if len(a) <= N // 3:
    ss = set([x for x in range(1, N + 1)])
    x = 3
    for y in a:
        res[y] = x
        ss.discard(x)
        x += 3
    ss = list(ss)
    for i in range(1, N + 1):
        if res[i]:
            continue
        res[i] = ss.pop()
    print((*res[1:]))
else:
    ss = set([x for x in range(1, N + 1)])
    x = 2
    for y in a:
        res[y] = x
        ss.discard(x)
        x += 3
        if x > N:
            break
    x = 3
    for y in a:
        if res[y]:
            continue
        res[y] = x
        ss.discard(x)
        x += 3
    ss = list(ss)
    for i in range(1, N + 1):
        if res[i]:
            continue
        res[i] = ss.pop()
    print((*res[1:]))

-from collections import defaultdict as dd -sys.setrecursionlimit(10**6) -e = dd(list) +e = [[] for _ in range(N + 1)] -cl = [0] * (N + 1) -vis = set() - - -def dfs(x): -    global cl -    global vis -    vis.add(x) +a = [1] +b = [] +s = [1] +vis = [0] * (N + 1) +table = [-1] * (N + 1) +table[1] = 1 +vis[1] = 1 +while len(s): +    x = s.pop() -        if y in vis: +        if vis[y]: -        cl[y] = (cl[x] + 1) % 2 -        dfs(y) - - -dfs(1) -bl = cl.count(1) -wh = N - bl +        vis[y] = 1 +        table[y] = table[x] ^ 1 +        if table[y]: +            a.append(y) +        else: +            b.append(y) +        s.append(y) +if len(a) > len(b): +    a, b = b, a -nm = [[] for _ in range(3)] -for i in range(1, N + 1): -    nm[i % 3].append(i) -# print(cl) -if bl <= N // 3: +if len(a) <= N // 3: +    ss = set([x for x in range(1, N + 1)]) +    x = 3 +    for y in a: +        res[y] = x +        ss.discard(x) +        x += 3 +    ss = list(ss) -        if cl[i]: -            res[i] = nm[0].pop() -        else: -            if len(nm[1]): -                res[i] = nm[1].pop() -            elif len(nm[2]): -                res[i] = nm[2].pop() -            else: -                res[i] = nm[0].pop() +        if res[i]: +            continue +        res[i] = ss.pop() -    exit(0) -if wh <= N // 3: +else: +    ss = set([x for x in range(1, N + 1)]) +    x = 2 +    for y in a: +        res[y] = x +        ss.discard(x) +        x += 3 +        if x > N: +            break +    x = 3 +    for y in a: +        if res[y]: +            continue +        res[y] = x +        ss.discard(x) +        x += 3 +    ss = list(ss) -        if cl[i] == 0: -            res[i] = nm[0].pop() -        else: -            if len(nm[1]): -                res[i] = nm[1].pop() -            elif len(nm[2]): -                res[i] = nm[2].pop() -            else: -                res[i] = nm[0].pop() +        if res[i]: +            continue +        res[i] = ss.pop() -    exit(0) -# print(nm) -# print(cl, nm) -f = 0 -for i in range(1, N + 1): -    if cl[i]: -        if len(nm[1]): -            res[i] = nm[1].pop() -        else: -            res[i] = nm[0].pop() -    else: -        if len(nm[2]): -            res[i] = nm[2].pop() -        else: -            res[i] = nm[0].pop() -print((*res[1:]))