#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1'000'000'007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

int N;
vector<vector<int>> G;
vector<int> depths;
vector<int> ans;

void dfs_depth(int cur, int prv){
    for(int nxt : G[cur]){
        if(nxt == prv) continue;
        depths[nxt] = depths[cur] + 1;
        dfs_depth(nxt, cur);
    }
}

void myfill(int one, int two){
    int cnt = 0;
    REP(i, N) if(ans[i] == 3) cnt++;
    int thr = N - one - two;
    vector<int> rem;
    REP(i, one) rem.push_back(1);
    REP(i, two) rem.push_back(2);
    REP(i, thr - cnt) rem.push_back(3);
    REP(i, N){
        if(ans[i] == 0){
            assert(!rem.empty());
            ans[i] = rem.back();
            rem.pop_back();
        }
    }
}

void myfill(int one, int two, int thr){
    for(int i=0; i<N; i++){
        if(depths[i]%2==0){
            if(one > 0){
                ans[i] = 1;
                one--;
            }
            else ans[i] = 3;
        }else{
            if(two > 0){
                ans[i] = 2;
                two--;
            }
            else ans[i] = 3;
        }
    }
}


int main(){
    cin >> N;
    G.resize(N);
    depths.resize(N);
    ans.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_depth(0, -1);
    int M = N / 3;
    int one = M, two = M, thr = M;
    if(N%3 > 0) one++;
    if(N%3 > 1) two++;
    //cerr << one << " " << two << " " << thr << endl;

    int ev = 0, od = 0;
    for(int depth : depths){
        if(depth%2==0) ev++;
        else od++;
    }

    if(one > ev){
        //cerr << "CASE 0" << endl;
        REP(i, N) if(depths[i]%2==0){
            ans[i] = 3;
        }
        myfill(one, two);
    }
    else if(two > od){
        //cerr << "CASE 1" << endl;
        REP(i, N) if(depths[i]%2==1){
            ans[i] = 3;
        }
        myfill(one, two);
    }else{
        //cerr << "CASE 2" << endl;
        myfill(one, two, thr);
    }
    //cerr << ans << endl;

    vector<int> ones, twos, thrs;
    for(int i=1; i<=N; i++){
        if(i%3==0) thrs.push_back(i);
        if(i%3==1) ones.push_back(i);
        if(i%3==2) twos.push_back(i);
    }

    vector<int> ansans(N);
    for(int i=0; i<N; i++){
        if(ans[i] == 1){
            ansans[i] = ones.back();
            ones.pop_back();
        }
        if(ans[i] == 2){
            ansans[i] = twos.back();
            twos.pop_back();
        }
        if(ans[i] == 3){
            ansans[i] = thrs.back();
            thrs.pop_back();
        }
    }
    for(int i=0; i<N; i++)
        cout << ansans[i] << " ";
    cout << endl;

    //for(int i=0; i<N; i++)
    //    cout << ansans[i]%3 << " ";
    //cout << endl;
    return 0;
}


Measured memory_bytes: 19320