#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
 
vector<int>g[200010]; 
int dist[200010];
int ans[200010];

int main(void){
    int n;
    cin>>n;
    for(int i=0;i<200010;i++)dist[i]=(int)1e9;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if(n==2 || n==3){
        for(int i=1;i<=n;i++){
            if(i==n)cout<<i<<endl;
            else cout<<i<<" ";
        }
        return 0;
    }
    queue<P>que;
    dist[1]=0;
    que.push(P(1,0));
    while(!que.empty()){
        P p = que.front();
        que.pop();
        int now = p.first;
        int cost = p.second;
        for(int i=0;i<g[now].size();i++){
            int next_node = g[now][i];
            if(dist[next_node]!=1000000000)continue;
            dist[next_node]=cost+1;
            que.push(P(next_node,dist[next_node]));
        }
    }
    vector<int>red,blue;
    for(int i=1;i<=n;i++){
        if(dist[i]%2==0)red.push_back(i);
        else blue.push_back(i);
    }
    int r = red.size();
    int b = blue.size();
    int c = n/3;
    int i_r = 0,i_b=0;
    if(r > c){
        if(b > c){
            for(i_r = 0;i_r<r;i_r++){
                if(3*i_r+1>n)break;
                ans[red[i_r]]=3*i_r+1;
            }
            for(i_b = 0;i_b<b;i_b++){
                if(3*i_b+2>n)break;
                ans[blue[i_b]]=3*i_b+2;
            }
            int index = 1;
            for(int i=i_r;i<r;i++){
                ans[red[i]]=3*index;
                index++;
            }
            for(int i=i_b;i<b;i++){
                ans[blue[i]]=3*index;
                index++;
            }
            for(int i=1;i<=n;i++){
                if(i==n)cout<<ans[i]<<endl;
                else cout<<ans[i]<<" ";
            }
        }
        else{
            int index = 1;
            for(int i=i_b;i<b;i++){
                ans[blue[i]]=3*index;
                index++;
            }
            for(i_r = 0;i_r<r;i_r++){
                if(3*index>n)break;
                ans[red[i_r]]=3*index;
                index++;
            }
            index = 0;
            for(;i_r<r;i_r++){
                if(3*index+1>n)break;
                ans[red[i_r]]=3*index+1;
                index++;
            }
            index = 0;
            for(;i_r<r;i_r++){
                if(3*index+2>n)break;
                ans[red[i_r]]=3*index+2;
                index++;
            }
            for(int i=1;i<=n;i++){
                if(i==n)cout<<ans[i]<<endl;
                else cout<<ans[i]<<" ";
            }
        }
    }
    else{
        int index = 1;
        for(int i=i_r;i<r;i++){
            ans[red[i]]=3*index;
            index++;
        }
        for(i_b = 0;i_b<b;i_b++){
            if(3*index>n)break;
            ans[blue[i_b]]=3*index;
            index++;
        }
        index = 0;
        for(;i_b<b;i_b++){
            if(3*index+1>n)break;
            ans[blue[i_b]]=3*index+1;
            index++;
        }
        index = 0;
        for(;i_b<b;i_b++){
            if(3*index+2>n)break;
            ans[blue[i_b]]=3*index+2;
            index++;
        }
        for(int i=1;i<=n;i++){
            if(i==n)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }
    return 0;
}



Measured memory_bytes: 17780