#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
//long long mo = 1e9 + 7;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    ll N;
    cin >> N;
    vector<vector<ll>> v(N);
    ll a,b;
    rep(i,N-1){
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ll q = N/3;
    ll r = N % 3;
    ll one=q,two=q,zero=q;
    if(r == 1){
        one++;
    }else if(r == 2){
        one++;
        two++;
    }
    queue<pair<ll,ll>> que;
    vector<ll> color(N,-1);
    que.push(pair<ll,ll>(0,0));
    while(!que.empty()){
        pair<ll,ll> pr = que.front();
        ll p = pr.first;
        ll c = pr.second;
        que.pop();
        if(color[p] != -1)continue;
        color[p] = c;//c^ll(1);
        rep(i,v[p].size()){
            if(color[v[p][i]] != -1)continue;
            que.push(pair<ll,ll>(v[p][i], c^ll(1)));
        }
    }
    ll cnt_a=0,cnt_b=0;
    rep(i,N){
        if(color[i] == 0)cnt_a++; else cnt_b++; 
    }
    queue<ll>ol,tl,zl;
    for(int i=1; i<=N ;i++){
        if(i%3 == 0){
            zl.push(i);
        }else if(i%3 == 1){
            ol.push(i);
        }else{
            tl.push(i);
        }
    }
    vector<ll> ans(N);
    if(cnt_a > N/3 && cnt_b > N/3){
        rep(i,N){
            if(color[i] == 0){
                if(!ol.empty()){
                    ans[i] = ol.front();
                    ol.pop();
                    one--;
                }else{
                    if(!zl.empty()){

                    ans[i] = zl.front();
                    zl.pop();
                    }
                }
            }else{
                if(!tl.empty()){
                    ans[i] = tl.front();
                    tl.pop();
                    two--;
                }else{
                    if(!zl.empty()){

                    ans[i] = zl.front();
                    zl.pop();
                    }
                }
            }
        }
    }else if(cnt_a <= N/3){
        rep(i,N){
            if(color[i] == 0){
                /*if(one > 0){
                    ans[i] = ol.front();
                    ol.pop();
                    one--;
                }else{*/
                    if(!zl.empty()){

                    ans[i] = zl.front();
                    zl.pop();
                    }
                //}
            }else{
                if(!tl.empty()){
                    ans[i] = tl.front();
                    tl.pop();
                    two--;
                }else if(!ol.empty()){
                    ans[i] = ol.front();
                    ol.pop();
                }else{
                    if(!zl.empty()){

                    ans[i] = zl.front();
                    zl.pop();
                    }
                }
            }
        }
    }else if(cnt_b <= N/3){
        rep(i,N){
            if(color[i] == 0){
                if(!ol.empty()){
                    ans[i] = ol.front();
                    ol.pop();
                    one--;
                }else if(!tl.empty()){
                    ans[i] = tl.front();
                    tl.pop();
                }else{
                    if(!zl.empty()){
                    ans[i] = zl.front();
                    zl.pop();
                    }
                }
            }else{
                /*if(two > 0){
                    ans[i] = tl.front();
                    tl.pop();
                    two--;
                }else{*/
                    if(!zl.empty()){

                    ans[i] = zl.front();
                    zl.pop();
                    }
                //}
            }
        }
    }

    /*
    vector<ll> dis(N,-1);
    ll a, b;
    rep(i,N-1){
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ll q = N/3;
    ll r = N % 3;
    ll rr = 0;
    
    ll zero = q;
    ll one=q, two=q;
    if(r == 1){
        one++;
    }else if(r == 2){
        one++;
        two++;
    }
    vector<ll> ans(N, 0);
    vector<ll> used(N+1,0);
    vector<ll> zz,oo,tt,any;
    rep(j,N){
        if(used[j+1] != 0)continue;
        queue<pair<ll,ll>> que;
        vector<ll> res;
        que.push(pair<ll,ll>(j,0));
        while(!que.empty()){
            pair<ll,ll> pr = que.front();
            ll p = pr.first;
            ll d = pr.second;
            que.pop();
            if(dis[p] != -1)continue;
            dis[p] = d;
            rep(i,v[p].size()){
                if(dis[v[p][i]] != -1)continue;
                if(d+1 == 3){
                    res.push_back(v[p][i]);
                }
                que.push(pair<ll,ll>(v[p][i], d+1));
            }
            if(d+1 == 3){
                break;
            }
        }
        
        zz.push_back(j);
        used[j+1] = 1;
        rep(i,res.size()){
            any.push_back(res[i]);
            used[res[i]+1] = 1;
        }
    }
    ll k = 3;
    vector<ll> used2(N+1,0);
    rep(i,zz.size()){
        ans[zz[i]] = k;
        used2[k]=1;
        k *= 3;
    }
    k /= 3;
    if(k > N+1){
        cout << -1 << endl;
        return 0;
    }
    rep(i,N){
        if(ans[i] != 0)continue;
        int j=0;
        while(used[j] == 1){
            j++;
        }
        ans[i] = j; 
    }*/
    rep(i,N){
        cout << ans[i] << " ";
    }
    cout << endl;
    //cout << min(mina+minb,mind) << endl;
}


Measured memory_bytes: 19560