// グラフ

#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr int INF = 1000000000 + 8;
constexpr int NONE = 0, RED = 1, BLUE = -1;

class Graph {
   private:
    struct edge {
        int to;
        int cost;
        edge(int i, int c = 1) : to(i), cost(c) {}
    };
    vector<vector<edge>> edges;
    vector<int> colors;
    int reds, blues;

   public:
    Graph(int n) { edges.resize(n); };
    int size() const { return edges.size(); };
    int countEdge() const {
        int count = 0;
        for (auto &&i : edges)
            for (auto &&j : i) count++;
        return count;
    }
    void addDirectedEdge(int from, int to, int cost = 1) {
        edges[from].push_back(edge(to, cost));
    }
    void addEdge(int from, int to, int cost = 1) {
        addDirectedEdge(from, to, cost);
        addDirectedEdge(to, from, cost);
    }
    bool colorizeBipartite(int s = 0) {
        reds = 0;
        blues = 0;

        colors.assign(size(), NONE);
        stack<int> stk;
        stk.push(s);
        colors[s] = RED;
        reds++;

        while (!stk.empty()) {
            const int p = stk.top();
            stk.pop();
            for (auto &&edge : edges[p]) {  // すべての隣接する頂点を調べる
                const int np = edge.to;
                // 隣接する頂点が無色なら今の頂点とは別の色で塗る
                if (colors[np] == NONE) {
                    stk.push(np);
                    colors[np] = -1 * colors[p];
                    switch (colors[np]) {
                        case RED:
                            reds++;
                            break;
                        case BLUE:
                            blues++;
                            break;
                    }
                }
            }
        }
        return true;
    }

    void solve() {
        colorizeBipartite();

        vector<int> p(size());

        deque<int> q012, q102, q210;

        array<vector<int>, 3> vals;
        for (int i = 1; i <= size(); i++) {
            vals[i % 3].push_back(i);
        }

        q012.insert(q012.end(), vals[0].begin(), vals[0].end());
        q012.insert(q012.end(), vals[1].begin(), vals[1].end());
        q012.insert(q012.end(), vals[2].begin(), vals[2].end());

        q102.insert(q102.end(), vals[1].begin(), vals[1].end());
        q102.insert(q102.end(), vals[0].begin(), vals[0].end());
        q102.insert(q102.end(), vals[2].begin(), vals[2].end());

        q210.insert(q210.end(), vals[2].begin(), vals[2].end());
        q210.insert(q210.end(), vals[1].begin(), vals[1].end());
        q210.insert(q210.end(), vals[0].begin(), vals[0].end());

        deque<int> q;
        if (reds <= size() / 3) {
            q = q012;
        } else if (blues <= size() / 3) {
            q = q210;
        } else {
            q = q102;
        }

        for (int i = 0; i < size(); i++) {
            switch (colors[i]) {
                case RED:
                    p[i] = q.front();
                    q.pop_front();
                    break;
                case BLUE:
                    p[i] = q.back();
                    q.pop_back();
                    break;
            }
        }

        for (auto &&i : p) {
            cout << i << " ";
        }
        cout << endl;
    }
};

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

    int n;
    cin >> n;

    Graph g(n);

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

        g.addEdge(a - 1, b - 1);
    }

    g.solve();
}


Measured memory_bytes: 27876