#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define CEIL(a, b) ((a) + (b)-1) / (b)

vector<vi> c;
vector<vi> G;
vi d;

void dfs(ll i, ll p)
{
    REP(j, G[i].size())
    {
        if (G[i][j] != p)
        {
            c[i].push_back(G[i][j]);
            d[G[i][j]] = d[i] + 1;
            dfs(G[i][j], i);
        }
    }
}

int main()
{
    ll N;
    cin >> N;
    vi a(N - 1), b(N - 1);
    REP(i, N - 1)
    {
        cin >> a[i] >> b[i];
    }

    G = vector<vi>(N + 1);
    REP(i, N - 1)
    {
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    c = vector<vi>(N + 1);
    d = vi(N + 1);
    dfs(1, 0);

    ll x = 0;
    ll y = 0;
    for (ll i = 1; i <= N; ++i)
    {
        if (d[i] % 2 == 0)
        {
            ++x;
        }
        else
        {
            ++y;
        }
    }
    ll m0 = N / 3;
    ll m1 = CEIL(N, 3);
    ll m2 = N - m0 - m1;

    vi ans(N);
    ll z0 = 3;
    ll z1 = 1;
    ll z2 = 2;
    if (x < m1)
    {
        for (ll i = 1; i <= N; ++i)
        {
            if (d[i] % 2 == 0)
            {
                ans[i - 1] = z0;
                z0 += 3;
            }
            else
            {
                if (z1 <= N)
                {
                    ans[i - 1] = z1;
                    z1 += 3;
                }
                else if (z2 <= N)
                {
                    ans[i - 1] = z2;
                    z2 += 3;
                }
                else
                {
                    ans[i - 1] = z0;
                    z0 += 3;
                }
            }
        }
    }
    else if (y < m2)
    {
        for (ll i = 1; i <= N; ++i)
        {
            if (d[i] % 2 == 1)
            {
                ans[i - 1] = z0;
                z0 += 3;
            }
            else
            {
                if (z1 <= N)
                {
                    ans[i - 1] = z1;
                    z1 += 3;
                }
                else if (z2 <= N)
                {
                    ans[i - 1] = z2;
                    z2 += 3;
                }
                else
                {
                    ans[i - 1] = z0;
                    z0 += 3;
                }
            }
        }
    }
    else
    {
        for (ll i = 1; i <= N; ++i)
        {
            if (d[i] % 2 == 0)
            {
                if (z1 <= N)
                {
                    ans[i - 1] = z1;
                    z1 += 3;
                }
                else
                {
                    ans[i - 1] = z0;
                    z0 += 3;
                }
            }
            else
            {
                if (z2 <= N)
                {
                    ans[i - 1] = z2;
                    z2 += 3;
                }
                else
                {
                    ans[i - 1] = z0;
                    z0 += 3;
                }
            }
        }
    }

    OUTA(ans, N);
}

Measured memory_bytes: 32256