#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

vector<int> g[201000];
int modeList[201000];
int res[201000];


P dfs(int v, int prev, int mode){
    int num1 = 0, num2 = 0;
    modeList[v] = mode;
    if(mode == 0){
        num1++;
    }
    else{
        num2++;
    }

    for(auto u: g[v]){
        if(u == prev){
            continue;
        }
        else{
            P ret = dfs(u, v, 1-mode);
            num1 += ret.fs; num2 += ret.sc;
        }
    }
    return P(num1, num2);
}


int main(){
    int N;  cin >> N;
    for(int i = 0; i < N-1; i++){
        int a, b;   cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    P x = dfs(0, 0, 0);

    if(x.fs * 2 < x.sc){
        queue<int> mode1, mode2;
        for(int i = 1; i <= N; i++){
            if(i % 3 == 0){
                mode1.push(i);
            }
            else{
                mode2.push(i);
            }
        }
        for(int i = 0; i < N; i++){
            if(modeList[i] == 0){
                res[i] = mode1.front();
                mode1.pop();
            }
            else{
                if(mode2.empty()){
                    res[i] = mode1.front();
                    mode1.pop();
                }
                else{
                    res[i] = mode2.front();
                    mode2.pop();
                }
            }
        }
    }
    else if(x.fs > x.sc * 2){
        queue<int> mode1, mode2;
        for(int i = 1; i <= N; i++){
            if(i % 3 == 0){
                mode1.push(i);
            }
            else{
                mode2.push(i);
            }
        }
        for(int i = 0; i < N; i++){
            if(modeList[i] == 0){
                if(mode2.empty()){
                    res[i] = mode1.front();
                    mode1.pop();
                }
                else{
                    res[i] = mode2.front();
                    mode2.pop();
                }
            }
            else{
                res[i] = mode1.front();
                mode1.pop();
            }
        }
    }
    else{
        queue<int> mode1, mode2, mode3;
        for(int i = 1; i <= N; i++){
            if(i % 3 == 0){
                mode3.push(i);
            }
            else if(i % 3 == 1){
                mode1.push(i);
            }
            else{
                mode2.push(i);
            }
        }
        for(int i = 0; i < N; i++){
            if(modeList[i] == 0){
                if(mode1.empty()){
                    res[i] = mode3.front();
                    mode3.pop();
                }
                else{
                    res[i] = mode1.front();
                    mode1.pop();
                }
            }
            else{
                if(mode2.empty()){
                    res[i] = mode3.front();
                    mode3.pop();
                }
                else{
                    res[i] = mode2.front();
                    mode2.pop();
                }
            }
        }
    }


    for(int i = 0; i < N; i++){
        cout << res[i] << " ";
    }
    cout << endl;


    return 0;
}


Measured memory_bytes: 23940