#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
ll n;
ll d[400010];
bool done[400010] = {0};
vector<vector<ll>> t(400010);
void dfs(ll v){
    done[v] = 1;
    for(ll i:t[v]){
        if (done[i]) continue;
        d[i] = d[v]+1;
        dfs(i);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    ll a,b;
    rep(i,n-1){
        cin >> a >> b;
        a--;
        b--;
        t[a].push_back(b);
        t[b].push_back(a);
    }
    d[0] = 0;
    dfs(0);
    queue<ll> q0,q1,q2;
    rep(i,1,n+1){
        if (i%3 == 0){
            q0.push(i);
        }
        else if (i%3 == 1){
            q1.push(i);
        }
        else{
            q2.push(i);
        }
    }
    vector<ll> ans(n,0);
    ll g1 = 0,g2 = 0;
    rep(i,n){
        if (d[i]%2 == 0) g1++;
        else g2++;
    }
    if (g1 > n/3 && g2 > n/3){
        rep(i,n){
            if (d[i]%2 == 0){
                if (!q1.empty()){
                    ans[i] = q1.front();
                    q1.pop();
                }
                else{
                    ans[i] = q0.front();
                    q0.pop();
                }
            }
            else{
                if (!q2.empty()){
                    ans[i] = q2.front();
                    q2.pop();
                }
                else{
                    ans[i] = q0.front();
                    q0.pop();
                }
            }
        }
    }else if (g1 <= n/3){
        int c;
        rep(i,n){
            if (d[i]%2 == 0){
                ans[i] = q0.front();
                q0.pop();
            }
            else{
                if (!q1.empty()){
                    ans[i] = q1.front();
                    q1.pop();
                }
                else if (!q2.empty()){
                    ans[i] = q2.front();
                    q2.pop();
                }
                else{
                    ans[i] = q0.front();
                    q0.pop();
                }
            }
        }
    }else{
        rep(i,n){
            if (d[i]%2 == 1){
                ans[i] = q0.front();
                q0.pop();
            }
            else{
                if (!q1.empty()){
                    ans[i] = q1.front();
                    q1.pop();
                }
                else if (!q2.empty()){
                    ans[i] = q2.front();
                    q2.pop();
                }
                else{
                    ans[i] = q0.front();
                    q0.pop();
                }
            }
        }
    }
    rep(i,n-1){
        cout << ans[i] << " ";
    }
    cout << ans[n-1] << "\n";
}


Measured memory_bytes: 23936