#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int mod = 1e9 + 7;
const int inf = 2e18;

signed main() {
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> dist(N, -1);
    dist[0] = 0;
    queue<int> bfs;
    bfs.push(0);
    while (!bfs.empty()) {
        int now = bfs.front();
        bfs.pop();
        for (int temp : G[now]) {
            if (dist[temp] == -1) {
                dist[temp] = dist[now] + 1;
                bfs.push(temp);
            }
        }
    }
    set<int> even, odd;
    for (int i = 0; i < N; i++) {
        if (dist[i] % 2 == 0) even.insert(i);
        else odd.insert(i);
    }
    vector<int> ans(N, -1);
    if (even.size() > N / 3 && odd.size() > N / 3) {
        int count = 1;
        for (auto temp : even) {
            if (count > N) break;
            ans[temp] = count;
            count += 3;
        }
        count = 2;
        for (auto temp : odd) {
            if (count > N) break;
            ans[temp] = count;
            count += 3;
        }
        count = 3;
        for (int i = 0; i < N; i++) {
            if (ans[i] == -1) {
                ans[i] = count;
                count += 3;
            }
        }
    } else if (even.size() <= N / 3) {
        int three = 3;
        for (auto temp : even) {
            ans[temp] = three;
            three += 3;
        }
        int count = 1;
        for (auto temp : odd) {
            if (count > N) break;
            ans[temp] = count;
            if (count % 3 == 1) ++count;
            else if (count % 3 == 2) count += 2;
        }
        for (int i = 0; i < N; i++) {
            if (ans[i] == -1) {
                ans[i] = three;
                three += 3;
            }
        }
    } else {
        int three = 3;
        for (auto temp : odd) {
            ans[temp] = three;
            three += 3;
        }
        int count = 1;
        for (auto temp : even) {
            if (count > N) break;
            ans[temp] = count;
            if (count % 3 == 1) ++count;
            else if (count % 3 == 2) count += 2;
        }
        for (int i = 0; i < N; i++) {
            if (ans[i] == -1) {
                ans[i] = three;
                three += 3;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        cout << ans[i] << (i == N - 1 ? '\n' : ' ');
    }
}

Measured memory_bytes: 26216