#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18

template <typename T>
struct Graph {
    int V, E;
    struct Edge {
        int from, to;
        T cost;
    };
    vector<vector<Edge>> edge;
    vector<vector<T>> dist;
    vector<Edge> es;

    Graph(int V, int E) : V(V), E(E) {
        edge.assign(V, vector<Edge>(0));
        dist.assign(V, vector<T>(0));
    }

    void input(bool is_direct, bool inputc, bool index0 = false) {
        int a, b;
        T c = 0;
        for (int i = 0; i < E; i++) {
            cin >> a >> b;
            if (inputc) cin >> c;
            if (!index0) a--, b--;
            edge[a].push_back((Edge){a, b, c});
            es.push_back((Edge){a, b, c});
            if (!is_direct) {
                edge[b].push_back((Edge){b, a, c});
                es.push_back((Edge){b, a, c});
            }
        }
        if (!is_direct) E *= 2;
    }

    void add_edge(int from, int to, T cost, bool is_direct) {
        edge[from].push_back({from, to, cost});
        es.push_back({from, to, cost});
        if (!is_direct) {
            edge[to].push_back({to, from, cost});
            es.push_back({to, from, cost});
            E++;
        }
        E++;
    }

    vector<int> red, blue;
    void coloring(int r = 0, bool color = 0) {
        static vector<bool> visited(V, false);
        visited[r] = true;
        if (color) red.push_back(r);
        if (!color) blue.push_back(r);

        for (auto& e : edge[r]) {
            int to = e.to;
            if (visited[to]) continue;
            coloring(to, !color);
        }
    }

    unordered_map<int, int> mp;
    void solve() {
        coloring();
        vector<int> v[3], index(3, 0);
        for (int i = 1; i <= V; i++) v[i % 3].push_back(i);
        if (red.size() <= V / 3) {
            for (int i = 0; i < red.size(); i++) mp[red[i]] = v[0][index[0]++];
            for (int i = 0; i < blue.size(); i++) {
                if (index[0] < v[0].size())
                    mp[blue[i]] = v[0][index[0]++];
                else if (index[1] < v[1].size())
                    mp[blue[i]] = v[1][index[1]++];
                else
                    mp[blue[i]] = v[2][index[2]++];
            }
        } else if (blue.size() <= V / 3) {
            for (int i = 0; i < blue.size(); i++) mp[blue[i]] = v[0][index[0]++];
            for (int i = 0; i < red.size(); i++) {
                if (index[0] < v[0].size())
                    mp[red[i]] = v[0][index[0]++];
                else if (index[1] < v[1].size())
                    mp[red[i]] = v[1][index[1]++];
                else
                    mp[red[i]] = v[2][index[2]++];
            }
        } else {
            for (int i = 0; i < red.size(); i++) {
                if (index[1] < v[1].size())
                    mp[red[i]] = v[1][index[1]++];
                else
                    mp[red[i]] = v[0][index[0]++];
            }
            for (int i = 0; i < blue.size(); i++) {
                if (index[2] < v[2].size())
                    mp[blue[i]] = v[2][index[2]++];
                else
                    mp[blue[i]] = v[0][index[0]++];
            }
        }
        for (int i = 0; i < V; i++) {
            cout << mp[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    int N;
    cin >> N;
    Graph<int> g(N, N - 1);
    g.input(false, false);
    g.solve();
    return 0;
}

Measured memory_bytes: 35500