#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vecll>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
#define MM " "
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}


vector<vec> g;
int col[210000];
int dfs(int x,int p,int c){
    col[x]=c;
    for(auto e:g[x]){
        if(e==p)continue;
        dfs(e,x,c^1);
    }
}
main(){
    ios
    int n=in();
    g.resize(n+1);
    rep(i,n-1){
        int a=in(),b=in();
        g[a].pb(b);
        g[b].pb(a);
    }
    queue<int> a[3];
    rep2(i,1,n){
        a[i%3].push(i);
    }
    int b=0,w=0;
    dfs(1,0,1);
    // rep2(i,1,n)cout<<col[i]<<" ";
    // cout<<endl;
    rep2(i,1,n){
        if(col[i])b++;
        else w++;
    }
    vec ans(n+1);
    if(b<=n/3){
        vec used(n+1);
        int now=3,p=1;
        rep2(i,1,n){
            if(col[i]){
                ans[i]=now;
                now+=3;
                used[now-3]=1;
            }
        }
        rep2(i,1,n){
            if(col[i]==0){
                while(used[p])p++;
                ans[i]=p;
                p++;
            }
        }
    }
    else if(w<=n/3){
        vec used(n+1);
        int now=3,p=1;
        rep2(i,1,n){
            if(!col[i]){
                ans[i]=now;
                now+=3;
                used[now-3]=1;
            }
        }
        rep2(i,1,n){
            if(col[i]){
                while(used[p])p++;
                ans[i]=p;
                p++;
            }
        }
    }
    else{
        rep2(i,1,n){
            if(col[i]){
                if(a[1].empty()){
                    ans[i]=a[0].front();
                    a[0].pop();
                }
                else{
                    ans[i]=a[1].front();
                    a[1].pop();
                }
            }
            else{
                if(a[2].empty()){
                    ans[i]=a[0].front();
                    a[0].pop();
                }
                else{
                    ans[i]=a[2].front();
                    a[2].pop();
                }
            }
        }
    }
    rep2(i,1,n){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}


Measured memory_bytes: 15472