#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct  UndirectedGraph{
   vector<vector<int>> g;
   vector<int> clr;//two clor -> 1 and -1
   vector<int> dis;
   int V;
 
   UndirectedGraph(int V) : V(V),
   g(vector<vector<int>>(V)),
   clr(vector<int>(V,0))
   {}
 
   //don't add (v,u) after adding (u,v)
   void add_edge(int u,int v){
       g[u].push_back(v);
       g[v].push_back(u);
   }
 
 
   //dfs for judging bipartite
   bool dfs_nib(int v,int c){
       clr[v]=c;
       for(auto x:g[v]){
           if(clr[x]==c) return false;
           if(clr[x]==0 && !dfs_nib(x,-c) ) return false;
       }
       return true;
   }
   bool isBipartite(){
       bool ret=true;
       for(int i=0;i<V;i++)if(clr[i]==0){
           if(!dfs_nib(i,1)){
               ret=false;break;
           }
       }
       return ret;
   }
 
   //distance
   void bfs(int st){
       dis=vector<int>(V,INF);
       vector<bool> checked(V,false);
       dis[st]=0;checked[st]=true;
       queue<int> q;
       q.push(st);
       while(!q.empty()){
           auto now=q.front();q.pop();
           for(auto x:g[now]){
               if(checked[x]) continue;
               checked[x]=true;
               dis[x]=dis[now]+1;
               q.push(x);
           }
       }
   }
 
   vector<int> color(){
       return clr;
   }
};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;cin>>n;
    UndirectedGraph g(n);
    rep(i,n-1){
        int u,v;cin>>u>>v;u--,v--;
        g.add_edge(u,v);
    }
    g.isBipartite();
    auto v=g.color();
    int a=0,b=0;
    rep(i,n){
        if(v[i]<0) b++;
        else a++;
    }
    if(a==1 or b==1){
        // star
        rep(i,n){
            cout<<i+1<<(i+1==n?'\n':' ');
        }
        return 0;
    }
    
    int p[3];
    rep(i,3) p[i]=n/3;
    if(n%3==1) p[0]++;
    if(n%3==2) p[0]++,p[1]++;

    vector<int> ans(n,-1);
    if(a>p[2] and b>p[2]){    
        rep(i,n){
            if(v[i]<0){
                if(p[0]){
                    p[0]--;ans[i]=p[0]*3+1;
                }else{
                    p[2]--;ans[i]=p[2]*3+3;
                }
            }
            else{
                if(p[1]){
                    p[1]--;ans[i]=p[1]*3+2;
                }else{
                    p[2]--;ans[i]=p[2]*3+3;
                }
            }
        }
    }
    else{
        //多いほうの色
        int m;
        if(a>b){
            m=1;
        }else{
            swap(a,b);
            m=-1;
        }
        rep(i,n){
            if(v[i]!=m){
                ans[i]=3*p[2];
                p[2]--;
            }
            else{
                if(p[0]){
                    p[0]--;
                    ans[i]=3*p[0]+1;
                }
                else if(p[1]){
                    p[1]--;
                    ans[i]=3*p[1]+2;
                }
                else{
                    ans[i]=p[2]*3;
                    p[2]--;
                }
            }
        }
        assert(*min_element(ALL(ans))==1 and *max_element(ALL(ans))==n);
    }
    
    rep(i,n){
        cout<<ans[i]<<(i+1==n?'\n':' ');
    }
    return 0;
}


Measured memory_bytes: 15600