//#define DEBUG
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define BSET(a, p) ((a) | (1ll << (p)))
#define BCHK(a, p) ((a) & (1ll << (p)))
#define BXOR(a, p) ((a) ^ (1ll << (p)));
#define BREM(a, p) (BCHK(a, p)?(BXOR(a, p)):(a))
#define BSHO(a, N) (bitset<N>(a))

#define fi first
#define sc second 
#define pb push_back


#ifdef DEBUG
    #define dbg(s) {s;}
    #define PRELUDE
#endif

#ifndef DEBUG 
    #define PRELUDE { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
    #define dbg(s)
    #define endl "\n"
#endif

#define int ll
#define i32 int32_t

#define RBTTYPE int
#define ordered_set tree<RBTTYPE, null_type, less<RBTTYPE>, rb_tree_tag,tree_order_statistics_node_update> 
// Ordered set docs:
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;

// To remove randomization use 0 below:
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int ri(int x) { // from [0, n-1]
    return uniform_int_distribution<int>(0, x - 1)(rng);
}

inline ld rf() { // from [0, 1]
    return uniform_real_distribution<ld>(0, 1)(rng);
}

ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 

const ll mod = 1e9 + 7;

ll modexp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % mod;
        ex >>= 1ll;
        x = (x * x) % mod;
    }
    return ans;
}

const int maxn = 2e5 + 7;

const ll inf = 1e9 + 7;
int n;
vector<int> graph[maxn];
int col[maxn];

void dfs(int ver, int colo)
{
    for(auto x:graph[ver])
    {
        if(col[x]==-1)
        {
            col[x] = colo;
            dfs(x,1-colo);
        }
    }
}
int ans[maxn];

void assign_col(int ty)
{
    int u = 3;
    for(int i=1;i<=n;i++)
    {
        if(col[i]==ty) {
            ans[i] = u;
            u += 3;
        }
    }

    int v = 1;
    for(int i=1;i<=n;i++)
    {
        if(col[i]!=ty) {
            ans[i] = v;
            v++;
            if (v % 3 == 0 && v < u)
                v++;
        }
    }
}

void assign_col2()
{
    memset(ans,-1, sizeof(ans));
    int v = 1;
    int u = 2;
    for(int i=1;i<=n;i++)
    {
        if(col[i]==0) {
            ans[i] = v;
            v+=3;
        }
        else {
            ans[i] = u;
            u+=3;
        }
    }
    u = 3;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==-1 || ans[i]>n)
        {
            ans[i] = u;
            u+=3;
        }
    }
}

void solve()
{
    cin>>n;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    memset(col,-1,sizeof(col));
    col[1] = 0;
    dfs(1,1);

    int odd = 0;
    int eve = 0;
    for(int i=1;i<=n;i++){
        assert(col[i]!=-1);
        if(col[i]==0)
            eve++;
        else
            odd++;
    }

    //cout<<eve<<odd<<endl;

    int c = n/3;
    if(eve<=c)
    {
        assign_col(0);
    }
    else if(odd<=c)
    {
        assign_col(1);
    } else{
        assign_col2();
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
}

i32 main() {
    //freopen("<file>.in", "r", stdin);
    //freopen("<file>.out", "w", stdout);
    
    PRELUDE;
    int t = 1;
    //cin>>t;
    while(t--)
        solve();
}


Measured memory_bytes: 20992