// 解き直し.
// https://img.atcoder.jp/hitachi2020/editorial.pdf
// C++14(GCC 5.4.1)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 202020;
int d[MAX]; // 頂点 1 からの 距離 を 保存.
int c[MAX]; // 距離が奇数: 1, 距離が偶数: 0.
int ans[MAX];

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    d[s] = 0;    // スタート地点は, 距離ゼロを指定.
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 3. 各頂点を色分け(※解説通り).
    int red = 0, blue = 0;
    rep(i, N) if(d[i] & 1) c[i] = 1, red++;
    blue = N - red;
    
    // 4. 頂点への番号付け.
    // 4-1. 赤色, 青色 が, (N / 3)個 より 多い.
    if(red > N / 3 && blue > N / 3){
        int rIdx = 1, bIdx = 2;
        rep(i, N){
            // 赤色.
            if(c[i] && rIdx <= N) ans[i] = rIdx, rIdx += 3;
            // 青色.
            if(!c[i] && bIdx <= N) ans[i] = bIdx, bIdx += 3;
        }
        int oIdx = 3;
        rep(i, N){
            // まだ割り当てしてない頂点に番号付け.
            if(!ans[i] && oIdx <= N) ans[i] = oIdx, oIdx += 3;
        }
    }
    
    // 4-2. 赤色 が, (N / 3)個 以下.
    if(red <= N / 3){
        int rIdx = 3;
        rep(i, N){
            // 赤色.
            if(c[i] && rIdx <= N) ans[i] = rIdx, rIdx += 3;
        }
        // まだ割り当てしてない頂点に番号付け.
        rep(i, N){
            if(!ans[i] && rIdx <= N) ans[i] = rIdx, rIdx += 3;
        }
        int oIdx = 1;
        rep(i, N){
            if(!ans[i] && oIdx <= N) ans[i] = oIdx, oIdx += 3;
        }
        oIdx = 2;
        rep(i, N){
            if(!ans[i] && oIdx <= N) ans[i] = oIdx, oIdx += 3;
        }
    }
    
    
    // 4-3. 青色 が, (N / 3)個 以下.
    if(blue <= N / 3){
        int bIdx = 3;
        rep(i, N){
            // 青色.
            if(!c[i] && bIdx <= N) ans[i] = bIdx, bIdx += 3;
        }
        // まだ割り当てしてない頂点に番号付け.
        rep(i, N){
            if(!ans[i] && bIdx <= N) ans[i] = bIdx, bIdx += 3;
        }
        int oIdx = 1;
        rep(i, N){
            if(!ans[i] && oIdx <= N) ans[i] = oIdx, oIdx += 3;
        }
        oIdx = 2;
        rep(i, N){
            if(!ans[i] && oIdx <= N) ans[i] = oIdx, oIdx += 3;
        }
    }
    
    // 5. 出力.
    rep(i, N){
        printf("%d", ans[i]);
        if(i < N - 1) printf(" ");
    }
    return 0;
    
}

Measured memory_bytes: 15988