#include <bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef unsigned long long int ullint;
std::string YesNo[] = {"No","Yes"};
#define loop(i,N) for(int i=0; i<(N); i++)
template<typename T>
auto sort_all(T& v) { return std::sort(v.begin(),v.end()); }
template<typename T>
auto sum_all(const T& v) { auto z = v[0]; z = 0;
    return std::accumulate(v.begin(),v.end(),z); }
template<typename T>
auto input( std::size_t N,
            const std::vector<T>& head={},
            const std::vector<T>& tail={}) {
    auto s = head.size();
    auto t = tail.size();
    std::vector<T> v;
    v.reserve(s+N+t);
    v.insert(v.end(), head.begin(), head.end());
    v.resize(s+N);
    loop(i,N) std::cin >> v[s+i];
    v.insert(v.end(), tail.begin(), tail.end());
    return std::move(v);
}
class range {
    typedef int Int;
    Int start, stop, step;
    void initialize() {
        auto sign = (step >= 0) ? 1 : -1;
        stop = start + ((stop-start-sign)/step + 1) * step;
        if ((stop-start) * step <= 0) stop = start;
    }
public:
    range(Int start, Int stop, Int step=1) : start(start), stop(stop), step(step) {
        initialize();
    }
    range(Int stop) : start(0), stop(stop), step(1) { initialize(); }
    struct iterator {
        Int i, step;
        Int& operator*() { return i; }
        iterator& operator++() { i += step; return *this; }
        bool operator!=(const iterator& v) { return i != v.i; }
    };
    iterator begin() { return {start, step}; }
    iterator end()   { return {stop, step}; }
};
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x)
{
    return std::make_pair(-x.first, -x.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator+(
    const std::pair<T1,T2>& x,
    const std::pair<T1,T2>& y)
{
    return std::make_pair(x.first+y.first, x.second+y.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x + (-y);
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator+=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    x.first += y.first;
    x.second += y.second;
    return x;
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator-=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x += (-y);
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& cout, const std::pair<T1,T2>& data)
{
    cout << "(" << data.first << ", " << data.second << ")";
    return cout;
}
template<typename T>
std::ostream& operator<<(std::ostream& cout, const std::vector<T>& data)
{
    cout << "[";
    if (data.size() == 0) {}
    else if (data.size() == 1) { cout << data[0]; } 
    else {
        cout << data[0];
        for (auto itr=data.begin()+1; itr!=data.end(); ++itr) {
            cout << ", " << *itr;
        }
    }
    cout << "]";
    return cout;
}

typedef llint Int;

int main(void)
{
    int N;
    cin >> N;
    vector<set<int>> neighbors(N);
    for (auto i: range(N-1)) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        neighbors[a].insert(b);
        neighbors[b].insert(a);
    }

    vector<tuple<int,int,int>> pool({make_tuple(0,0,-1)});
    vector<int> Nres = {
        N/3,
        N/3 + int(N%3 >= 1),
        N/3 + int(N%3 >= 2)};

    vector<vector<int>> layer(2);
    while (!pool.empty()) {
        auto node = pool.back();
        pool.pop_back();
        auto k = get<0>(node);
        auto depth = get<1>(node);
        auto parent = get<2>(node);

        layer[depth%2].push_back(k);
        for (auto n: neighbors[k]) {
            if (n != parent) {
                pool.push_back(make_tuple(n,depth+1,k));
            }
        }
    }
    //cout << layer[0] << " " << layer[1] << endl;

    vector<int> ans(N,0);
    vector<int> cur({3,1,2});
    if (layer[0].size() > N/3 && layer[1].size() > N/3) {
        for (auto p: range(2)) {
            for (auto i: layer[p]) {
                if (cur[p+1] <= N) {
                    ans[i] = cur[p+1];
                    cur[p+1] += 3;
                } else {
                    ans[i] = cur[0];
                    cur[0] += 3;
                }
            }
        }
    } else {
        int p = 0;
        if (layer[1].size() <= N/3) {
            p = 1;
        }
        for (auto i: layer[p]) {
            ans[i] = cur[0];
            cur[0] += 3;
        }
        for (auto i: layer[(p+1)%2]) {
            if (cur[0] <= N) {
                ans[i] = cur[0];
                cur[0] += 3;
            } else if (cur[1] <= N) {
                ans[i] = cur[1];
                cur[1] += 3;
            } else {
                ans[i] = cur[2];
                cur[2] += 3;
            }
        }
    }

    cout << ans[0];
    for (auto i: range(1,N)) {
        cout << " " << ans[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 33392