#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <unordered_map>
#include <iterator>
#include <stack>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <cstring>
#include <bitset>

#include <random>

using namespace std;
void dout() { cerr << endl; }
typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

using ll = long long;
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

void precalc() {}

//#define solvsh
//#define multi
#ifdef solvsh

const int MAXN = 5e5 + 10;

void solve() {

}

#else

const int MAXN = 2e5 + 19;
vector<int> g[MAXN];

int colors[MAXN];

int n;


int answr[MAXN];

int last1 = 1;
int last2 = 2;
int last3 = 3;


int c_c[2];

void dfs(int vertex, int par = -1) {

    if (c_c[0] <= c_c[1]) {
        if (colors[vertex] == 0) {
            answr[vertex] = last3;
            last3 += 3;
        } else {
            if (last2 <= n) {
                answr[vertex] = last2;
                last2 += 3;
            } else if (last1 <= n) {
                answr[vertex] = last1;
                last1 += 3;
            } else {
                answr[vertex] = last3;
                last3 += 3;
            }
        }
    } else {
        if (colors[vertex] == 1) {
            answr[vertex] = last3;
            last3 += 3;
        } else {
            if (last2 <= n) {
                answr[vertex] = last2;
                last2 += 3;
            } else if (last1 <= n) {
                answr[vertex] = last1;
                last1 += 3;
            } else {
                answr[vertex] = last3;
                last3 += 3;
            }
        }
    }


    for (auto out : g[vertex]) {
        if (out == par)
            continue;

        dfs(out, vertex);
    }
}

void dfs_c(int ver, int color, int par = -1) {
    colors[ver] = color;
    c_c[color]++;
    for (auto out : g[ver]){
        if (out != par){
            dfs_c(out, 1 - color, ver);
        }
    }
}

void dfs_st(int ver, int par = -1){

    if (c_c[0] <= c_c[1]) {
        if (colors[ver] == 0 && last2 <= n){
            answr[ver] = last2;
            last2 += 3;
        } else if (colors[ver] == 1 && last1 <= n){
            answr[ver] = last1;
            last1 += 3;
        } else {
            answr[ver] = last3;
            last3 += 3;
        }
    } else {
        if (colors[ver] == 1 && last2 <= n) {
            answr[ver] = last2;
            last2 += 3;
        } else if (colors[ver] == 0 && last1 <= n) {
            answr[ver] = last1;
            last1 += 3;
        } else {
            answr[ver] = last3;
            last3 += 3;
        }
    }

    for (auto out : g[ver]){
        if (out != par){
            dfs_st(out, ver);
        }
    }
}

void solve() {
    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_c(1, 0);
    int x = n / 3;
    if (min(c_c[0], c_c[1]) <= x) {
        dfs(1, 1);
    } else {
        dfs_st(1);
    }

    for (int i = 1; i <= n; ++i) {
        cout << answr[i] << " ";
    }
}

#endif

void multisolve() {
    int t;
    cin >> t;

    while (t--)
        solve();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

    precalc();


#ifdef multi
    multisolve();
#else
    solve();
#endif

#ifdef LOCAL
    //cout << '\n' << (double)clock() / CLOCKS_PER_SEC << '\n';
#endif
}

Measured memory_bytes: 19328