/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll col[200010] = {};
vector<ll> tree[200010];
ll a[200010], b[200010];


void dfs(ll cur, ll par, ll d){
    // print(cur);
    col[cur] = d % 2;
    for(auto &e: tree[cur]){
        if(e == par) continue;
        dfs(e, cur, (d+1) % 2);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    rep(i,0,N-1){
        // a[i] = 1; b[i] = i+2;
        // print(a[i], b[i]);
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        tree[a[i]].push_back(b[i]);
        tree[b[i]].push_back(a[i]);
    }
    dfs(0, -1, 0);
    ll c1 = 0, c2 = 0, c3 = 0;
    rep(i,1,N+1){
        if(i % 3 == 0) c3++;
        else if(i % 3 == 1) c1++;
        else c2++;
    }
    // printa(col, N);
    ll ans[200010] = {};
    ll cnt0 = 0, cnt1 = 0;
    rep(i,0,N){
        if(col[i] == 0) cnt0++;
        else cnt1++;
    }
    ll num[200010] = {};
    if(cnt0 > cnt1){
        if(cnt1 < c2){
            rep(i,0,N){
                if(col[i] == 1){
                    num[i] = 3;
                    c3--;
                }
            }
        }else{
            rep(i,0,N){
                if(col[i] == 1){
                    if(c2 > 0){
                        c2--;
                        num[i] = 2;
                    }else{
                        num[i] = 3;
                        c3--;
                    }
                }
            }
        }
        rep(i,0,N){
            if(col[i] == 0){
                if(c2 > 0){
                    c2--;
                    num[i] = 2;
                }else if(c1 > 0){
                    c1--;
                    num[i] = 1;
                }else{
                    c3--;
                    num[i] = 3;
                }
            }
        }

    }else{
        if(cnt0 < c2){
            rep(i,0,N){
                if(col[i] == 0){
                    num[i] = 3;
                    c3--;
                }
            }
        }else{
            rep(i,0,N){
                if(col[i] == 0){
                    if(c2 > 0){
                        c2--;
                        num[i] = 2;
                    }else{
                        num[i] = 3;
                        c3--;
                    }
                }
            }
        }
        rep(i,0,N){
            if(col[i] == 1){
                if(c2 > 0){
                    c2--;
                    num[i] = 2;
                }else if(c1 > 0){
                    c1--;
                    num[i] = 1;
                }else{
                    c3--;
                    num[i] = 3;
                }
            }
        }
    }

    if(c1 != 0 || c2 != 0 || c3 != 0){
        print("Oops");
        print(c1,c2,c3);
        exit(1);
    }

    ll v1 = 1, v2 = 2, v3 = 3;
    rep(i,0,N){
        if(num[i] == 1){
            ans[i] = v1;
            v1 += 3;
        }else if(num[i] == 2){
            ans[i] = v2;
            v2 += 3;
        }else{
            ans[i] = v3;
            v3 += 3;
        }
    }
    printa(ans, N);


    

}

Measured memory_bytes: 24960