#include <bits/stdc++.h>

#define rep(i,c) for(int i = 0; i < (int)c; ++i)
using llint = long long int ;
using namespace std;

class Graph //DFSとBFS
{
private:
    std::vector<std::vector<int>> relation;
    std::queue<int> que;//キュー　先に入れたものを先に取り出す first in first out
public:
    std::vector<int> dist;//負の値は未探索 グラフの距離(BFSのときだけ)
    std::vector<int> first_order;//行きがけ順
    std::vector<int> last_order;//帰りがけ順
    Graph(int M,int order);//グラフを初期化　relationはグラフの辺
    void MakeDirect(int x,int y);//無効グラフを作る
    void BFS(int x);//幅優先探索をする。距離はdistに格納
    void DFS(int x,int& first_ptr,int& last_ptr);//深さ優先探索
};

Graph::Graph(int M,int order=0):relation(M),dist(M,-1){
    if(order){
        first_order.resize(M);
        last_order.resize(M);
    }
}
void Graph::MakeDirect(int x,int y){
    relation[x].push_back(y);
    relation[y].push_back(x);
}
void Graph::BFS(int x){
    dist[x]=0;//xを根として距離を０とする
    que.push(x);//キューに根ｘを追加
    while(!que.empty()){//キューが空になるまで
        int v=que.front();//キューから取り出す
        que.pop();//キューから削除
        for(int e:relation[v]){//取り出したvから距離１でいけるところを探索
            if(dist[e]!=-1) continue;//探索したことある場所はのぞく
            que.push(e);//キューに格納
            dist[e]=dist[v]+1;//距離をタス
        }
    }
}
void Graph::DFS(int x,int& first_ptr ,int& last_ptr){
    dist[x]=1;//探索済みは１にする
    first_order[x]=first_ptr++;//行きがけ順
    for(int e:relation[x]){//取り出したvから距離１でいけるところを探索
        if(dist[e]==1) continue;
        DFS(e,first_ptr,last_ptr);//再帰で探索
    }
    last_order[x]=last_ptr++;//帰りがけ順
}



int main(){
    int N;
    cin>>N;
    Graph tr(N);
    
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        tr.MakeDirect(a-1,b-1);
    }
    
    tr.BFS(0);
    int count=0;
    rep(i,N){
        if(tr.dist[i] %2==1) count++;
    }
    
    int ans[N];
    int bai3=3;
    int amari1=1;
    int amari2=2;
    if(count<=(N/3)){
        rep(i,N){
            if(tr.dist[i]%2==1){
                ans[i]=bai3;
                bai3+=3;
            }
            else{
                if(amari1>N&&amari2>N){
                    ans[i]=bai3;
                    bai3+=3;
                }
                else if(amari1>N){
                    ans[i]=amari2;
                    amari2+=3;
                }
                else{
                    ans[i]=amari1;
                    amari1+=3;
                }
            }
        }
    }

    else if( (N-count) <= (N/3) ){
        rep(i,N){
            if(tr.dist[i]%2==0){
                ans[i]=bai3;
                bai3+=3;
            }
            else{
                if(amari1>N&&amari2>N){
                    ans[i]=bai3;
                    bai3+=3;
                }
                else if(amari1>N){
                    ans[i]=amari2;
                    amari2+=3;
                }
                else{
                    ans[i]=amari1;
                    amari1+=3;
                }
            }
        }
    }

    else{
        rep(i,N){
            if(tr.dist[i]%2==1){
                if(amari1<=N){
                    ans[i]=amari1;
                    amari1+=3;
                }
                else{
                    ans[i]=bai3;
                    bai3+=3;
                }
            }
            else{
                if (amari2<=N)
                {
                    ans[i]=amari2;
                    amari2+=3;
                }
                else{
                    ans[i]=bai3;
                    bai3+=3;
                }
                
            }
        }
    }

    rep(i,N)cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 15220