#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
        if(b&1)res = res * x % MOD;
        x = x * x % MOD;
        b>>=1;
    }
    return res;
}

ll modinv(ll x){
    return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
}
void outendl(){
    was_output = false;
    cout << endl;
}
ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
}

template<class t>
istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
}

template<class t, class u>
istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
}

int main(){
    ll n = in();
    queue<int> que[3];
    rep(i,1,n+1){
        que[i%3].push(i);
    }
    auto isok = [&](int p){
        return que[p].size();
    };
    auto pop = [&](int p){
        int res = que[p].front();
        que[p].pop();
        return res;
    };
    vvector<int> edges(n);
    rep(i,n-1){
        int a = in()-1;
        int b = in()-1;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    vector<int> ans(n);
    {
        vector<int> fast(n,INF);
        stack<int> st;
        st.push(0);
        fast[0] = 0;
        while(st.size()){
            int d = st.top();
            st.pop();
            foreach(i,edges[d]){
                if(chmin(fast[i],fast[d]+1)){
                    st.push(i);
                }
            }
        }
        int cnt = 0;
        foreach(i,fast){
            i%=2;
            if(i)++cnt;
        }
        if(cnt<=n/3){
            rep(i,n){
                if(fast[i]){
                    ans[i] = pop(0);
                }else{
                    if(isok(1)){
                        ans[i] = pop(1);
                    }else if(isok(2)){
                        ans[i] = pop(2);
                    }else{
                        ans[i] = pop(0);
                    }
                }
            }
        }else if(n-cnt<=n/3){
            rep(i,n){
                if(!fast[i]){
                    ans[i] = pop(0);
                }else{
                    if(isok(1)){
                        ans[i] = pop(1);
                    }else if(isok(2)){
                        ans[i] = pop(2);
                    }else{
                        ans[i] = pop(0);
                    }
                }
            }
        }else{
            rep(i,n){
                if(fast[i]){
                    if(isok(1))ans[i] = pop(1);
                    else ans[i] = pop(0);
                }else{
                    if(isok(2))ans[i] = pop(2);
                    else ans[i] = pop(0);
                }
            }
        }
    }

    foreach(i,ans)output(i);
    outendl();
    return 0;
}


Measured memory_bytes: 15208