#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

vector<vector<int>> G;
queue<int> a, b; //a true b false
void dfs(int v, int parv, bool visin){

    for(int i: G[v]){
        if( i == parv ) continue;
        if(visin){
            b.push(i);
            dfs(i, v, !visin);
        }
        else{
            a.push(i);
            dfs(i, v, !visin);
        }

    }

}


int main(){
    int N;
    cin >> N;
    G.resize(N+1);
    int tmp1, tmp2;
    for(int i = 0; i < N-1; i++){
        cin >> tmp1 >> tmp2;
        G[tmp1].push_back(tmp2);
        G[tmp2].push_back(tmp1);
    }

    a.push(1);
    dfs(1, 0, true);

    int cna, cnb, M, k, tmp;
    cna = a.size();
    cnb = b.size();
    vector<int> ans(N+1);
    if(N%3 == 0){
        M = N/3;
        if(min(cna, cnb) >= M){
            for (int i = 0; i < M; i++) {
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*i + 1;
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*i + 2;
            }
            k = 1;
            while(!a.empty()){
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*k;
                k++;
            }
            while(!b.empty()){
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*k;
                k++;
            }
        }
        else{
            if(cna > cnb){
                for (int i = 0; i < M; i++) {
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 2;
                }
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
            else{
                for (int i = 0; i < M; i++) {
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 2;
                }
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
        }
    }
    else if(N%3 == 1){
        M = N/3;
        if(min(cna, cnb) >= M+1){
            for (int i = 0; i < M; i++) {
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*i + 1;
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*i + 2;
            }
            tmp = a.front();
            a.pop();
            ans[tmp] = 3*M + 1;
            k = 1;
            while(!a.empty()){
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*k;
                k++;
            }
            while(!b.empty()){
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*k;
                k++;
            }
        }
        else{
            if(cna > cnb){
                for (int i = 0; i < M; i++) {
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 2;
                }
                tmp = a.front(); a.pop();
                ans[tmp] = 3*M +1;
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
            else{
                for (int i = 0; i < M; i++) {
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 2;
                }
                tmp = b.front(); b.pop();
                ans[tmp] = 3*M +1;
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
        }        

    }
    else{
        M = N/3;
        if(min(cna, cnb) >= M+1){
            for (int i = 0; i < M+1; i++) {
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*i + 1;
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*i + 2;
            }
            k = 1;
            while(!a.empty()){
                tmp = a.front();
                a.pop();
                ans[tmp] = 3*k;
                k++;
            }
            while(!b.empty()){
                tmp = b.front();
                b.pop();
                ans[tmp] = 3*k;
                k++;
            }
        }
        else{
            if(cna > cnb){
                for (int i = 0; i < M+1; i++) {
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = a.front(); a.pop();
                    ans[tmp] = 3*i + 2;
                }
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
            else{
                for (int i = 0; i < M+1; i++) {
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 1;
                    tmp = b.front(); b.pop();
                    ans[tmp] = 3*i + 2;
                }
                k = 1;
                while(!a.empty()){
                    tmp = a.front();
                    a.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
                while(!b.empty()){
                    tmp = b.front();
                    b.pop();
                    ans[tmp] = 3*k;
                    k++;
                }
            }
        }        
    }

    for (int i = 1; i < N+1; i++) {
        printf("%d ", ans[i]);
    }


}

Measured memory_bytes: 20352