#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//dijkstra
ll MAX_V=2*1e5+5;//問題の条件による
struct edge {ll to, cost;};
typedef pair<ll, ll> P; // firstは最短距離、secondは頂点の番号
ll INF=1001001;
vector<vector<edge>> G(MAX_V); //辺のデータ G[a]={aからいける場所b,コストc}の集合
vector<ll> d(MAX_V); //始点からの距離
void dijkstra(ll s) {
    // greater<P>を指定することでfirstが小さい順に取り出せるようにする
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main(){
    ll n; cin>>n;
    ll one=n/3, two=n/3, zero=n/3;
    if(n%3==1){one++;}
    if(n%3==2){one++; two++;}
    rep(i,n-1){
        ll a,b; cin>>a>>b;
        G[a].push_back({b,1});
        G[b].push_back({a,1});
    }
    dijkstra(1);
    vector<ll> res(n,-1);
    ll cnt1=0, cnt2=0, cnt0=0;
    rep(i,n){
        if(d[i+1]%2==0){
            res[i]=1;
            cnt1++;
        }else{
            res[i]=2;
            cnt2++;
        }
    }
    
    if(cnt1>=one && cnt2>=two){
        rep(i,n){
            if(cnt0==zero) break;
            if(res[i]==1 && cnt1>one){
                res[i]=0;
                cnt1--;
                cnt0++;
            }else if(res[i]==2 && cnt2>two){
                res[i]=0;
                cnt2--;
                cnt0++;
            }
        }
    }else{
        if(cnt1<cnt2){
            rep(i,n) if(res[i]==1) res[i]=0;
            cnt0=cnt1;
            cnt1=0;
            rep(i,n){
                if(res[i]==2 && cnt0<zero){
                    res[i]=0;
                    cnt2--;
                    cnt0++;
                }else if(res[i]==2 && cnt1<one){
                    res[i]=1;
                    cnt2--;
                    cnt1++;
                }
            }
        }else{
            rep(i,n) if(res[i]==2) res[i]=0;
            cnt0=cnt2;
            cnt2=0;
            rep(i,n){
                if(res[i]==1 && cnt0<zero){
                    res[i]=0;
                    cnt1--;
                    cnt0++;
                }else if(res[i]==1 && cnt2<two){
                    res[i]=2;
                    cnt1--;
                    cnt2++;
                }
            }
        }
    }
    ll ichi=0, ni=0, rei=0;
    rep(i,n){
        if(res[i]==1){
            res[i]=ichi*3+1;
            ichi++;
           
        }else if(res[i]==2){
            res[i]=ni*3+2;
            ni++;
            
        }else{
            res[i]=rei*3+3;
            rei++;
            
        }
    }
    rep(j,n){
        if(j==0) cout<<res[j];
        else cout<<' '<<res[j];
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 22884