#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;


int nib[200001] = {0};
vll G[200001];

void dfs(int now,int d){
    nib[now] = d;
    for(auto x:G[now]){
        if(nib[x] == 0){
            dfs(x,d%2+1);
        }
    }
    return;
}

/*----------------------------------------------------------------*/
signed main(){

    int n;
    cin >> n;

    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].pb(b-1);
        G[b-1].pb(a-1);
    }

    if(n == 2){
        cout << "1 2" << endl;
        return 0;
    }else if(n == 3){
        cout << "1 2 3" << endl;
        return 0;
    }

    vll ans(n);
    dfs(0,1);

    // rep(i,n)cerr << nib[i] << " ";cerr << endl;

    int cnt1 = 0;
    int cnt2 = 0;
    rep(i,n){
        if(nib[i] == 1)cnt1++;
        if(nib[i] == 2)cnt2++;
    }

    // if(max(cnt1,cnt2) > (n+2)/3 + n/3){
    //     cout << -1 << endl;
    //     return 0;
    // }

    int k[3] = {};
    int m[3] = {};
    for(int i = 1;i <= n;i++)m[i%3]++;
    if(min(cnt1,cnt2) <= n/3){
        rep(i,n){
            if((nib[i] == 1 && cnt1 < cnt2) || (nib[i] == 2 && cnt1 > cnt2)){
                ans[i] = k[0]*3+3;
                k[0]++;
            }else{
                if(k[1] < m[1]){
                    ans[i] = k[1]*3+1;
                    k[1]++;
                }else if(k[2] < m[2]){
                    ans[i] = k[2]*3+2;
                    k[2]++;
                }else{
                    ans[i] = k[0]*3+3;
                    k[0]++;
                }
            }
        }
    }else if(cnt1 > cnt2){
        rep(i,n){
            if(nib[i] == 1){
                if(k[1] < m[1]){
                    ans[i] = k[1]*3+1;
                    k[1]++;
                }else{
                    ans[i] = k[0]*3+3;
                    k[0]++;
                }
            }else{
                if(k[2] < m[2]){
                    ans[i] = k[2]*3+2;
                    k[2]++;
                }else{
                    ans[i] = k[0]*3+3;
                    k[0]++;
                }
            }
        }
    }else{
        rep(i,n){
            if(nib[i] == 2){
                if(k[1] < m[1]){
                    ans[i] = k[1]*3+1;
                    k[1]++;
                }else{
                    ans[i] = k[0]*3+3;
                    k[0]++;
                }
            }else{
                if(k[2] < m[2]){
                    ans[i] = k[2]*3+2;
                    k[2]++;
                }else{
                    ans[i] = k[0]*3+3;
                    k[0]++;
                }
            }
        }
    }

    rep(i,n)cout << ans[i] << " ";cout << endl;

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://pakencamp-2019-day3.contest.atcoder.jp/tasks/pakencamp_2019_day3_c
// rm -r -f test;oj dl https://hitachi2020.contest.atcoder.jp/tasks/hitachi2020_a

Measured memory_bytes: 18048