#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

struct edge{int to,cost;};
int V;
const int MAX_V=200010;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii>> que;
    fill(d,d+V+10,mod);
    d[s]=0;
    que.push(pii(0,s));
    while(!que.empty()){
        pii p=que.top();
        que.pop();
        int v=p.S;
        if(d[v]<p.F)continue;
        rep(i,sz(G[v])){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(pii(d[e.to],e.to));
            }
        }
    }    
}

int main() {
    int n;
    cin >> n;
    V=n;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        G[a].pb({b,1});
        G[b].pb({a,1});
    }
    dijkstra(0);
    int now1=1;
    int now2=2;
    int now3=3;
    int num[n];
    int cnt=0;
    int mx1=n/3+(bool)(n%3);
    int mx3=n/3;
    int mx2=n-mx1-mx3;
    rep(i,n){
        if(d[i]%2)cnt++;
    }
    int cas=0;
    if(n-cnt<=mx3)cas=1;
    if(cnt<=mx3)cas=2;
    if(!cas){
        /*
        奇数は1,3より少ない
        偶数は2,3より少ない
        cnt==mx1>mx3
         */
        rep(i,n){
            if(d[i]%2){
                if(now1<=n){
                    num[i]=now1;
                    now1+=3;
                }
                else{
                    num[i]=now3;
                    now3+=3;
                }
            }
            else{
                if(now2<=n){
                    num[i]=now2;
                    now2+=3;
                }
                else{
                    num[i]=now3;
                    now3+=3;
                }
            }
        }
    }
    else if(cas==1){
        rep(i,n){
            if(d[i]%2){
                if(now1<=n){
                    num[i]=now1;
                    now1+=3;
                }
                else if(now2<=n){
                    num[i]=now2;
                    now2+=3;
                }
                else{
                    num[i]=now3;
                    now3+=3;
                }
            }
            else{
                if(now3<=n){
                    num[i]=now3;
                    now3+=3;
                }
            }
        }
    }
    else{
        rep(i,n){
            if(d[i]%2==0){
                if(now1<=n){
                    num[i]=now1;
                    now1+=3;
                }
                else if(now2<=n){
                    num[i]=now2;
                    now2+=3;
                }
                else{
                    num[i]=now3;
                    now3+=3;
                }
            }
            else{
                if(now3<=n){
                    num[i]=now3;
                    now3+=3;
                }
            }
        }
    }
    rep(i,n){
      	debug(d[i]);
        cout << num[i] << ' ';
    }
}

/*
すきなポケモンはカイリュー


 */





Measured memory_bytes: 17752