#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int N;
vv<int> tree;
vector<int> depth;

void dfs_pre(int v, int p) {
    for (int u : tree[v]) {
        if (u == p) continue;
        depth[u] = depth[v] + 1;
        dfs_pre(u, v);
    }
}

int main() {
    cin >> N;
    tree.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    depth.resize(N);
    dfs_pre(0, -1);
    array<int, 2> dpcnt = { 0, 0 };
    rep(i, N) dpcnt[depth[i] % 2]++;

    vector<int> r0, r1, r2;
    rep(i, 1, N + 1) {
        if (i % 3 == 0) r0.push_back(i);
        else if (i % 3 == 1) r1.push_back(i);
        else r2.push_back(i);
    }
    vector<int> ans(N);
    if (dpcnt[0] <= N / 3) {
        rep(i, N) {
            if (depth[i] % 2 == 0) {
                ans[i] = r0.back();
                r0.pop_back();
            }
        }
        rep(i, N) {
            if (depth[i] % 2 == 0) continue;
            else if (!r0.empty()) {
                ans[i] = r0.back();
                r0.pop_back();
            }
            else if (!r1.empty()) {
                ans[i] = r1.back();
                r1.pop_back();
            }
            else {
                ans[i] = r2.back();
                r2.pop_back();
            }
        }
    }
    else if (dpcnt[1] <= N / 3) {
        rep(i, N) {
            if (depth[i] % 2 == 1) {
                ans[i] = r0.back();
                r0.pop_back();
            }
        }
        rep(i, N) {
            if (depth[i] % 2 == 1) continue;
            else if (!r0.empty()) {
                ans[i] = r0.back();
                r0.pop_back();
            }
            else if (!r1.empty()) {
                ans[i] = r1.back();
                r1.pop_back();
            }
            else {
                ans[i] = r2.back();
                r2.pop_back();
            }
        }
    }
    else {
        rep(i, N) {
            if (depth[i] % 2 == 0) {
                if (!r1.empty()) {
                    ans[i] = r1.back();
                    r1.pop_back();
                }
                else {
                    ans[i] = r0.back();
                    r0.pop_back();
                }
            }
            else {
                if (!r2.empty()) {
                    ans[i] = r2.back();
                    r2.pop_back();
                }
                else {
                    ans[i] = r0.back();
                    r0.pop_back();
                }
            }
        }
    }

    rep(i, N) cout << ans[i] << (!--N ? '\n' : ' ');
}

Measured memory_bytes: 18808