#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

vector<vector<int>> g;
vector<pair<int, int>> depth;
void dfs(int now, int pre, int dep) {
    depth.emplace_back(dep, now);
    for (int nxt : g[now]) {
        if (nxt == pre) continue;
        dfs(nxt, now, dep ^ 1);
    }
}

int main() {
    int n;
    cin >> n;

    g.resize(n);
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1, 0);
    sort(all(depth));

    vector<int> ans(n, -1);
    int pos = 0, pre;
    int c1 = n / 3 + (n % 3 >= 1), c2 = n / 3 + (n % 3 >= 2), c0 = n / 3;

    int od = 0, ev = 0;
    rep(i, n) {
        (depth[i].first == 1 ? od : ev)++;
    }

    if (od <= c0) {
        rep(i, n) {
            int dep, idx;
            tie(dep, idx) = depth[i];
            if (dep == 0) {
                if (c1 > 0) {
                    ans[idx] = 1;
                    c1--;
                } else if (c2 > 0) {
                    ans[idx] = 2;
                    c2--;
                } else {
                    ans[idx] = 0;
                    c0--;
                }
            }
            if (dep == 1) {
                ans[idx] = 0;
                c0--;
            }
        }
    } else if (ev <= c0) {
        rep(i, n) {
            int dep, idx;
            tie(dep, idx) = depth[i];
            if (dep == 1) {
                if (c1 > 0) {
                    ans[idx] = 1;
                    c1--;
                } else if (c2 > 0) {
                    ans[idx] = 2;
                    c2--;
                } else {
                    ans[idx] = 0;
                    c0--;
                }
            }
            if (dep == 0) {
                ans[idx] = 0;
                c0--;
            }
        }
    } else {
        rep(i, n) {
            int dep, idx;
            tie(dep, idx) = depth[i];
            if (ans[idx] == 0) continue;
            if (dep == 0) {
                if (c1 > 0) {
                    ans[idx] = 1;
                    c1--;
                } else {
                    ans[idx] = 0;
                    c0--;
                }
            }
            if (dep == 1) {
                if (c2 > 0) {
                    ans[idx] = 2;
                    c2--;
                } else {
                    ans[idx] = 0;
                    c0--;
                }
            }
        }
    }

    int n0 = 3, n1 = 1, n2 = 2;
    rep(i, n) {
        if (ans[i] == 0) {
            ans[i] = n0;
            n0 += 3;
        } else if (ans[i] == 1) {
            ans[i] = n1;
            n1 += 3;
        } else if (ans[i] == 2) {
            ans[i] = n2;
            n2 += 3;
        }
    }

    rep(i, n) cout << ans[i] << " \n"[i == n - 1];
}


Measured memory_bytes: 18548