#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
ll INF = 1001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll N;
Graph G(200010);
ll A[200010];
ll B[200010];
ll d[200010];
ll p = 0,q = 0;

vector<queue<ll>> QS(3);
queue<ll> QUE;

void dijksttra(ll s){
    fill(d,d+200010,INF);
    d[s] = 0;
    QUE.push(s);
    while(QUE.size()){
        ll x = QUE.front();
        ll n = G[x].size();
        QUE.pop();
        rep(i,n){
            ll y = G[x][i];
            if(d[y] != INF) continue;
            d[y] = d[x] + 1;
            QUE.push(y);
        }
    }
}

int main(){
    cin >> N;
    rep(i,N-1){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        B[a]++;B[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dijksttra(0);
    rep(i,N){
        B[i] = d[i] % 2;
        if(B[i] == 0) q++;
        else p++;
    }
    FOR(i,1,N+1){
        QS[i % 3].push(i);
    }
    if(p <= N / (ll)3){
        rep(i,N){
            if(B[i] == 1){
                A[i] = QS[0].front();
                QS[0].pop();
            }
        }
        rep(i,N){
            if(B[i] == 0){
                rep(j,3){
                    if(QS[j].size() != 0){
                        A[i] = QS[j].front();
                        QS[j].pop();
                        break;
                    }
                }
            }
        }
    }else if(q <= N / (ll)3){
        rep(i,N){
            if(B[i] == 0){
                A[i] = QS[0].front();
                QS[0].pop();
            }
        }
        rep(i,N){
            if(B[i] == 1){
                rep(j,3){
                    if(QS[j].size() != 0){
                        A[i] = QS[j].front();
                        QS[j].pop();
                        break;
                    }
                }
            }
        }
    }else{
        rep(i,N){
            if(B[i] == 1){
                if(QS[1].size() == 0){
                    A[i] = QS[0].front();
                    QS[0].pop();
                    continue;
                }
                A[i] = QS[1].front();
                QS[1].pop();
            }else{
                if(QS[2].size() == 0){
                    A[i] = QS[0].front();
                    QS[0].pop();
                    continue;
                }
                A[i] = QS[2].front();
                QS[2].pop();
            }
        }
        rep(i,N){
            if(A[i] != 0) continue;
            rep(j,3){
                if(QS[j].size() != 0){
                    A[i] = QS[j].front();
                    QS[j].pop();
                }
            }
        }
    }
    rep(i,N){
        cout << A[i] << ' ';
    }
    cout << endl;
}


Measured memory_bytes: 20200