#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 200010;

int N;
vector<int> A, B;
vector<int> graph[MAX_N];

enum class RB { Red = 0, Blue };
vector<RB> color;  // 各頂点の色

// color の設定
static inline void dfs(int i, int prev, RB c) {
    color[i] = c;
    RB next_c = (c == RB::Red) ? RB::Blue : RB::Red;

    for(auto& next_i : graph[i]) {
        if(next_i == prev) { continue; }
        dfs(next_i, i, next_c);
    }
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.resize(N);
    B.resize(N);
    vector<int> ans(N, 0);
    REP(i, N-1) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    color.resize(N);
    // グラフの作成
    REP(i, N) {
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    dfs(0, 0, RB::Red);

    int cnt_r = 0, cnt_b = 0;
    REP(i, N) {
        if(color[i] == RB::Red) { cnt_r++; }
        else { cnt_b++; }
    }


    vector<int> n1, n2, n3;
    for(int i = 1; i <= N; ++i) {
        if(i % 3 == 1) { n1.push_back(i); }
        else if(i % 3 == 2) { n2.push_back(i); }
        else if(i % 3 == 0) { n3.push_back(i); }
    }

    if(cnt_r <= N / 3 || cnt_b <= N / 3) {
        RB conv = (cnt_r > cnt_b) ? RB::Red : RB::Blue;
        // 少ない方に % 3 = 0 を入れる
        REP(i, N) {
            if(color[i] == conv) {
                if(n1.size() > 0) {
                    ans[i] = n1[n1.size()-1];
                    n1.pop_back();
                }
                else if(n2.size() > 0) {
                    ans[i] = n2[n2.size()-1];
                    n2.pop_back();
                }
                else {
                    assert(n3.size() > 0);
                    ans[i] = n3[n3.size()-1];
                    n3.pop_back();
                }
            }
            else {
                assert(n3.size() > 0);
                ans[i] = n3[n3.size() - 1];
                n3.pop_back();
            }
        }
    }
    else {
        // Red に % 3 = 1 を、 Blue に % 3 = 2 を入れる
        REP(i, N) {
            if(color[i] == RB::Red) {
                if(n1.size() > 0) {
                    ans[i] = n1[n1.size()-1];
                    n1.pop_back();
                }
                else {
                    assert(n3.size() > 0);
                    ans[i] = n3[n3.size()-1];
                    n3.pop_back();
                }
            }
            else {
                if(n2.size() > 0) {
                    ans[i] = n2[n2.size()-1];
                    n2.pop_back();
                }
                else {
                    assert(n3.size() > 0);
                    ans[i] = n3[n3.size()-1];
                    n3.pop_back();
                }
            }
        }
    }

    REP(i, N) {
        printf("%lld%c", ans[i], (i == N-1) ? '\n' : ' ');
    }

    return 0;
}



Measured memory_bytes: 22760