/*It was very radiant,
Filled with light, always filled, baby
Everyone cheers,
They cheer again, toward us, yeah
Cause you yeah you
Your appearance, your smile, yeah
Night that has come, oh, that will soak me with a dream
Pulled on to a bright stage that shines in my eyes
I smile toward you like a doll
I have to withstand each dizzying step
This fear that I’ve overcome alone
It shines even brighter, our night

Most of all, this is beautiful
My circus
It gets dizzy in front of my eyes at times
More dangerous it gets, more it heats up
My circus
How much more beautiful would our night be
I’ll throw it at you, my heart

With no hesitation,
I give all of me to you, yeah
I extend my hand, so I can fly toward you
Cause you yeah you
Your two hands, your heart, yeah
Oh, I, oh, if you let me go
Fantasy crumbles, it will end
White clothes flutter, like flower leaves
When it gently blooms again in the distant
Comfortably as if walking on clouds
I’ll go toward you

Most of all, this is beautiful
My circus
It gets dizzy in front of my eyes at times
More dangerous it gets, more it heats up
My circus
How much more beautiful would our night be
I’ll throw it at you, my heart

Say goodnight yeah
Oh yeah oh yeah
Say goodnight yeah
I walk a bit more toward you
Say goodnight yeah
In this night, in this night, baby
Say goodnight yeah
Trust us, baby
White clothes flutter, like flower leaves
When it gently blooms again in the distant
Comfortably as if walking on clouds
I’ll go toward you

Most of all, this is beautiful
My circus
How much more riskier will each night be for us?
Exceptionally shining, my heart*/

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define for1(i, a, b) for(i = a; i <= b; ++i)
#define for0(i, a, b) for(i = a; i < b; ++i)
#define forw1(i, a, b) for(i = a; i >= b; --i)
#define forw0(i, a, b) for(i = a - 1; i >= b; --i)
#define fora(v, a) for(auto v : a)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

using namespace std;
using cd = complex<double>;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<cd> vcd;
typedef vector<ii> vii;
typedef vector<vector<int> > vvi;

const int modd1 = 1e9 + 7, modd2 = 998244353, maxn = 2e5 + 5, K = 26, inf = 1e9, infll = 1e18;
const double pi = acos(-1);
vi gr[maxn];
vi r, b;
int n, vis[maxn], ans[maxn];

void dfs(int u, int p, int t){
    if(t == 1){
        r.pb(u);    
    }    
    else{
        b.pb(u);
    }
    fora(v, gr[u]){
        if(v == p) continue;
        dfs(v, u, 3 - t);
    }
}

void solve(){
    int i, j, k, l, ck; cin >> n;
    for1(i, 1, n - 1){
        int u, v; cin >> u >> v; gr[u].pb(v); gr[v].pb(u);
    }
    dfs(1, 1, 1);
    ck = n / 3;
    if(r.size() <= ck){
        for0(i, 0, r.size()){
            ans[r[i]] = (i + 1) * 3; vis[(i + 1) * 3] = 1;
        }
        int id = 0;
        for1(i, 1, n){
            if(!vis[i]){
                ans[b[id]] = i; vis[i] = 1; id++;
            }
        }
        for1(i, 1, n){
            cout << ans[i] << ' ';
        }
        return;
    }
    if(b.size() <= ck){
        for0(i, 0, b.size()){
            ans[b[i]] = (i + 1) * 3; vis[(i + 1) * 3] = 1;
        }
        int id = 0;
        for1(i, 1, n){
            if(!vis[i]){
                ans[r[id]] = i; vis[i] = 1; id++;
            }
        }
        for1(i, 1, n){
            cout << ans[i] << ' ';
        }
        return;
    }
    int st = 1, id = 0;
    while(st <= n){
        ans[r[id]] = st; st += 3; id++;
    }
    st = 2, id = 0;
    while(st <= n){
        ans[b[id]] = st; st += 3; id++;
    }
    st = 3;
    fora(v, r){
        if(!ans[v]){
            ans[v] = st; st += 3;
        }
    }
    fora(v, b){
        if(!ans[v]){
            ans[v] = st; st += 3;
        }
    }
    for1(i, 1, n){
        cout << ans[i] << ' ';
    }
}

signed main() {
    //freopen(".INP", "r", stdin); 
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

Measured memory_bytes: 23916