# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)

# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)

# 0,1,2がk個ずつ



# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)

#   1-2,1-0,2-1,2-0,0-0はOKなので



# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合

#   2k以上の方に1,2を割り当てて、反対側をすべて0にする



# 両方とも(k,2k)の場合

# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める





def main():

    from collections import deque

    from itertools import chain

    import sys

    input = sys.stdin.readline



    # INPUT

    N = int(eval(input()))



    graph = tuple(set() for _ in range(N))

    for _ in range(N - 1):

        a, b = (int(x) - 1 for x in input().split())

        graph[a].add(b)

        graph[b].add(a)



    # BFS

    dq = deque([0])

    parity = [-1] * N

    parity[0] = 0



    vs = [[] for _ in range(2)]

    vs[0].append(0)



    while dq:

        v = dq.popleft()

        p = parity[v]

        np = 1 ^ p

        for u in graph[v]:

            if ~parity[u]: continue

            parity[u] = np

            vs[np].append(u)

            dq.append(u)



    # SOLVE

    k = N // 3  # 3の倍数の個数



    g1 = iter(list(range(1, N + 1, 3)))

    g2 = iter(list(range(2, N + 1, 3)))

    g3 = iter(list(range(3, N + 1, 3)))

    if len(vs[0]) <= k:

        # parity=0を3の倍数で埋める

        # 残りを余った数で埋める

        for v in vs[0]:

            parity[v] = next(g3)  # g3の方がvs[0]より数多い



        g123 = chain(g1, g2, g3)



        for v in vs[1]:

            parity[v] = next(g123)



    elif len(vs[1]) <= k:

        # parity=1を3の倍数で埋める

        # 残りを余った数で埋める

        for v in vs[1]:

            parity[v] = next(g3)  # g3の方がvs[1]より数多い



        g123 = chain(g1, g2, g3)



        for v in vs[0]:

            parity[v] = next(g123)



    else:

        # parity=0を(mod3=1)で埋める

        # parity=1を(mod3=2)で埋める

        # 残りを3の倍数で埋める



        g13 = chain(g1, g3)

        for v in vs[0]:

            parity[v] = next(g13)

            # k<=len(g1)<=k+1,len(vs[0])>=k+1

            # 右辺がg1だけだと不足する恐れ



        g23 = chain(g2, g3)

        for v in vs[1]:

            parity[v] = next(g23)

            # k<=len(g2)<=k+1,len(vs[1])>=k+1

            # 右辺がg2だけだと不足する恐れ



    print((*parity))





if __name__ == '__main__':

    main()

# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)

# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)

# 0,1,2がk個ずつ



# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)

#   1-2,1-0,2-1,2-0,0-0はOKなので



# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合

#   2k以上の方に1,2を割り当てて、反対側をすべて0にする



# 両方とも(k,2k)の場合

# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める





def main():

    from collections import deque

    from itertools import chain

    import sys

    input = sys.stdin.readline



    # INPUT

    N = int(eval(input()))



    graph = tuple(set() for _ in range(N))

    for _ in range(N - 1):

        a, b = (int(x) - 1 for x in input().split())

        graph[a].add(b)

        graph[b].add(a)



    # BFS

    dq = deque([0])

    parity = [-1] * N

    parity[0] = 0

    size_0 = 0

    while dq:

        v = dq.popleft()

        p = parity[v]

        if p == 0:

            size_0 += 1

        np = 1 ^ p

        for u in graph[v]:

            if ~parity[u]: continue

            parity[u] = np

            dq.append(u)



    # SOLVE

    k = N // 3  # 3の倍数の個数

    g1 = iter(list(range(1, N + 1, 3)))  # rangeのままだとchain(g1,g2,g3)としたときg3が途中から始まらない

    g2 = iter(list(range(2, N + 1, 3)))  # range != iteratorなので消費が共有されないため

    g3 = iter(list(range(3, N + 1, 3)))

    if size_0 <= k:  # parity=0を3の倍数で埋め,残りを余った数で埋める

        g123 = chain(g1, g2, g3)

        ret = (next(g3) if p == 0 else next(g123) for p in parity)



    elif N - size_0 <= k:  # parity=1を3の倍数で埋め,残りを余った数で埋める

        g123 = chain(g1, g2, g3)

        ret = (next(g3) if p == 1 else next(g123) for p in parity)



    else:  # parity=0を(mod3=1)で,parity=1を(mod3=2)で埋め,残りを3の倍数で埋める

        g13 = chain(g1, g3)

        g23 = chain(g2, g3)

        ret = (next(g13) if p == 0 else next(g23) for p in parity)



    print((*ret))





if __name__ == '__main__':

    main()

# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ
# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので
# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする
# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める
def main():
    from collections import deque
    from itertools import chain
    import sys

    input = sys.stdin.readline
    # INPUT
    N = int(eval(input()))
    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)
    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0
    vs = [[] for _ in range(2)]
    vs[0].append(0)
    while dq:
        v = dq.popleft()
        p = parity[v]
        np = 1 ^ p
        for u in graph[v]:
            if ~parity[u]:
                continue
            parity[u] = np
            vs[np].append(u)
            dq.append(u)
    # SOLVE
    k = N // 3  # 3の倍数の個数
    g1 = iter(list(range(1, N + 1, 3)))
    g2 = iter(list(range(2, N + 1, 3)))
    g3 = iter(list(range(3, N + 1, 3)))
    if len(vs[0]) <= k:
        # parity=0を3の倍数で埋める
        # 残りを余った数で埋める
        for v in vs[0]:
            parity[v] = next(g3)  # g3の方がvs[0]より数多い
        g123 = chain(g1, g2, g3)
        for v in vs[1]:
            parity[v] = next(g123)
    elif len(vs[1]) <= k:
        # parity=1を3の倍数で埋める
        # 残りを余った数で埋める
        for v in vs[1]:
            parity[v] = next(g3)  # g3の方がvs[1]より数多い
        g123 = chain(g1, g2, g3)
        for v in vs[0]:
            parity[v] = next(g123)
    else:
        # parity=0を(mod3=1)で埋める
        # parity=1を(mod3=2)で埋める
        # 残りを3の倍数で埋める
        g13 = chain(g1, g3)
        for v in vs[0]:
            parity[v] = next(g13)
            # k<=len(g1)<=k+1,len(vs[0])>=k+1
            # 右辺がg1だけだと不足する恐れ
        g23 = chain(g2, g3)
        for v in vs[1]:
            parity[v] = next(g23)
            # k<=len(g2)<=k+1,len(vs[1])>=k+1
            # 右辺がg2だけだと不足する恐れ
    print((*parity))


if __name__ == "__main__":
    main()

# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ
# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので
# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする
# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める
def main():
    from collections import deque
    from itertools import chain
    import sys

    input = sys.stdin.readline
    # INPUT
    N = int(eval(input()))
    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)
    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0
    size_0 = 0
    while dq:
        v = dq.popleft()
        p = parity[v]
        if p == 0:
            size_0 += 1
        np = 1 ^ p
        for u in graph[v]:
            if ~parity[u]:
                continue
            parity[u] = np
            dq.append(u)
    # SOLVE
    k = N // 3  # 3の倍数の個数
    g1 = iter(list(range(1, N + 1, 3)))  # rangeのままだとchain(g1,g2,g3)としたときg3が途中から始まらない
    g2 = iter(list(range(2, N + 1, 3)))  # range != iteratorなので消費が共有されないため
    g3 = iter(list(range(3, N + 1, 3)))
    if size_0 <= k:  # parity=0を3の倍数で埋め,残りを余った数で埋める
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 0 else next(g123) for p in parity)
    elif N - size_0 <= k:  # parity=1を3の倍数で埋め,残りを余った数で埋める
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 1 else next(g123) for p in parity)
    else:  # parity=0を(mod3=1)で,parity=1を(mod3=2)で埋め,残りを3の倍数で埋める
        g13 = chain(g1, g3)
        g23 = chain(g2, g3)
        ret = (next(g13) if p == 0 else next(g23) for p in parity)
    print((*ret))


if __name__ == "__main__":
    main()

-    vs = [[] for _ in range(2)] -    vs[0].append(0) +    size_0 = 0 +        if p == 0: +            size_0 += 1 -            vs[np].append(u) -    g1 = iter(list(range(1, N + 1, 3))) -    g2 = iter(list(range(2, N + 1, 3))) +    g1 = iter(list(range(1, N + 1, 3)))  # rangeのままだとchain(g1,g2,g3)としたときg3が途中から始まらない +    g2 = iter(list(range(2, N + 1, 3)))  # range != iteratorなので消費が共有されないため -    if len(vs[0]) <= k: -        # parity=0を3の倍数で埋める -        # 残りを余った数で埋める -        for v in vs[0]: -            parity[v] = next(g3)  # g3の方がvs[0]より数多い +    if size_0 <= k:  # parity=0を3の倍数で埋め,残りを余った数で埋める -        for v in vs[1]: -            parity[v] = next(g123) -    elif len(vs[1]) <= k: -        # parity=1を3の倍数で埋める -        # 残りを余った数で埋める -        for v in vs[1]: -            parity[v] = next(g3)  # g3の方がvs[1]より数多い +        ret = (next(g3) if p == 0 else next(g123) for p in parity) +    elif N - size_0 <= k:  # parity=1を3の倍数で埋め,残りを余った数で埋める -        for v in vs[0]: -            parity[v] = next(g123) -    else: -        # parity=0を(mod3=1)で埋める -        # parity=1を(mod3=2)で埋める -        # 残りを3の倍数で埋める +        ret = (next(g3) if p == 1 else next(g123) for p in parity) +    else:  # parity=0を(mod3=1)で,parity=1を(mod3=2)で埋め,残りを3の倍数で埋める -        for v in vs[0]: -            parity[v] = next(g13) -            # k<=len(g1)<=k+1,len(vs[0])>=k+1 -            # 右辺がg1だけだと不足する恐れ -        for v in vs[1]: -            parity[v] = next(g23) -            # k<=len(g2)<=k+1,len(vs[1])>=k+1 -            # 右辺がg2だけだと不足する恐れ -    print((*parity)) +        ret = (next(g13) if p == 0 else next(g23) for p in parity) +    print((*ret))