#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n;
    cin >> n;
    vector<vector<int>> edges(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges[u].emplace_back(v);
        edges[v].emplace_back(u);
    }
    vector<int> bi(n, -1);
    bi[0]                        = 0;
    function<void(int, int)> dfs = [&](int c, int p) {
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            bi[v] = 1 - bi[c];
            dfs(v, c);
        }
    };
    dfs(0, -1);

    vector<int> depth(n, -1);
    int maxd                          = 0;
    depth[0]                          = 0;
    function<void(int, int)> dfsdepth = [&](int c, int p) {
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            depth[v] = 1 + depth[c];
            chmax(maxd, depth[v]);
            dfsdepth(v, c);
        }
    };
    dfsdepth(0, -1);
    if (maxd <= 1) { // uni
        vector<int> ret(n);
        for (int i = 0; i < n; ++i) {
            ret[i] = i + 1;
        }
        for (int i = 0; i < n; ++i) {
            if (i != 0)
                cout << " ";
            cout << ret[i];
        }
        cout << "\n";
        return 0;
    }

    int cnta = 0, cntb = 0;
    for (int i = 0; i < n; ++i) {
        if (bi[i] == 0)
            cnta++;
        else
            cntb++;
    }
    int none = cnta > cntb ? cnta : cntb;
    int ntwo = cnta + cntb - none;

    vector<int> ret(n, -1);
    int one     = n / 3 + (n % 3 == 0 ? 0 : 1);
    int two     = n / 3 + (n % 3 < 2 ? 0 : 1);
    int thr     = n / 3;
    int oneused = 0;
    int twoused = 0;
    int thrused = 0;
    if (ntwo <= thr) {
        int idxt = cnta < cntb ? 0 : 1;
        // thr -= ntwo;
        for (int i = 0; i < n; ++i) {
            if (bi[i] == idxt) {
                ret[i] = thrused * 3 + 3;
                thrused++;
            } else {
                if (oneused < one) {
                    ret[i] = oneused * 3 + 1;
                    oneused++;
                } else if (twoused < two) {
                    ret[i] = twoused * 3 + 2;
                    twoused++;
                } else {
                    ret[i] = thrused * 3 + 3;
                    thrused++;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i != 0)
                cout << " ";
            cout << ret[i];
        }
        cout << "\n";
        return 0;
    }
    int idxone = cnta > cntb ? 0 : 1;
    for (int i = 0; i < n; ++i) {
        if (bi[i] == idxone) {
            if (none > one) {
                ret[i] = thrused * 3 + 3;
                thrused++;
                none--;
            } else {
                ret[i] = oneused * 3 + 1;
                oneused++;
            }
        } else {
            if (ntwo > two) {
                ret[i] = thrused * 3 + 3;
                thrused++;
                ntwo--;
            } else {
                ret[i] = twoused * 3 + 2;
                twoused++;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i != 0)
            cout << " ";
        cout << ret[i];
    }
    cout << "\n";
    // cout << one << " " << two << " " << thr << "\n";

    return 0;
}

Measured memory_bytes: 23296