#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

struct Edge {
    int to;
};
using Graph = vector<vector<Edge>>;

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

ll N, M, K, Q, W, H, L, R, C;
string S, T;

// 幅優先探索
vector<int> dist;  // 始点からの距離を記録
void bfs(const Graph &G, int s) {
    const int INF = 1e8;
    dist.assign((int)G.size(), INF);  // 初期化

    queue<int> que;
    que.emplace(s);  // sから探索する
    dist[s] = 0;
    while (que.size() != 0) {   // 幅優先探索
        int now = que.front();  // 現在の状態
        que.pop();
        for (auto e : G[now]) {
            if (dist[e.to] == INF) {  // 未探索の時のみ行う
                dist[e.to] = dist[now] + 1;
                que.emplace(e.to);
            }
        }
    }
}
int main() {
    int V;
    cin >> V;

    Graph G(V);
    for (int i = 0; i < V - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back({b});
        G[b].push_back({a});
    }

    bfs(G, 0);

    int a = 0;
    int b = 0;
    for (int i = 0; i < V; i++) {
        if (dist[i] % 2 == 0) {
            a++;
        } else {
            b++;
        }
    }

    vector<int> ans(V);
    int one = 1;
    int two = 2;
    int three = 3;
    if (a <= V / 3) {
        for (int i = 0; i < V; i++) {
            if (dist[i] % 2 == 0) {
                ans[i] = three;
                three += 3;
            } else {
                if (one <= V) {
                    ans[i] = one;
                    one += 3;
                } else if (two <= V) {
                    ans[i] = two;
                    two += 3;
                } else {
                    ans[i] = three;
                    three += 3;
                }
            }
        }
    } else if (b <= V / 3) {
        for (int i = 0; i < V; i++) {
            if (dist[i] % 2 == 1) {
                ans[i] = three;
                three += 3;
            } else {
                if (one <= V) {
                    ans[i] = one;
                    one += 3;
                } else if (two <= V) {
                    ans[i] = two;
                    two += 3;
                } else {
                    ans[i] = three;
                    three += 3;
                }
            }
        }
    } else {
        for (int i = 0; i < V; i++) {
            if (dist[i] % 2 == 1) {
                if (one <= V) {
                    ans[i] = one;
                    one += 3;
                } else {
                    ans[i] = three;
                    three += 3;
                }
            } else {
                if (two <= V) {
                    ans[i] = two;
                    two += 3;
                } else {
                    ans[i] = three;
                    three += 3;
                }
            }
        }
    }

    for (int i = 0; i < V; i++) {
        cout << ans[i];
        if (i != V - 1) cout << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 15220