#include <iostream>
#include <sstream>
#include <cassert>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----

//
// Provides data structures, algorithms related to directed and 
// undirected graphs and facilities for constructing graphs by reading from
// input streams. Adjacency list representation is used throughout.

/** Undirected graphs of a given edge weight type - e.g., int or long long .*/
template<class T>
class Graph
{
public:
    Graph(int _N, bool _directed = false, bool _weighted = false)
    {
        N = _N;
        directed = _directed;
        weighted = _weighted;

        Edges.resize(N + 1);
        if (weighted) {
            EdgeWeights.resize(N + 1);
        }
    }

    void ReadFromStream(istream& in)
    {
        int M = N - 1;

        for (int i = 0;i < M; i++) {
            int u, v;
            T weight;
            in >> u >> v;
            if (weighted) {
                in >> weight;
            }

            Edges[u].push_back(v);
            if (weighted) {
                EdgeWeights[u].push_back(weight);
            }

            if (!directed) {
                Edges[v].push_back(u);
                if (weighted) {
                    EdgeWeights[v].push_back(weight);
                }
            }
        }
    }

    int Size() const {
        return N;
    }

    vector<int> BFS(int source) const
    {
        vector<int> dist(N + 1, -1);
        queue<int> bfsQ;

        auto addToQ = [&bfsQ, &dist](int vertex, int d)
        {
            if (dist[vertex] < 0) {
                dist[vertex] = d;
                bfsQ.push(vertex);
            }
        };

        addToQ(source, 0);
        while (!bfsQ.empty()) {
            int v = bfsQ.front();
            bfsQ.pop();
            for (int i = 0;i < Edges[v].size(); i++) {
                addToQ(Edges[v][i], dist[v] + 1);
            }
        }

        return dist;
    }

    vector<T> Dijkstra(int source, T infinity) const
    {
        if (!weighted) {
            vector<int> bfs = BFS(source);
            vector<T> ret(N + 1);
            for (int i = 1;i <= N; i++)
                ret[i] = (T)(bfs[i]);

            return ret;
        }

        vector<T> dist(N + 1, infinity);
        vector<bool> processed(N + 1, false);
        priority_queue<pair<T, int> > heap;

        auto addToQ = [&heap, &dist](int v, T new_distance)
        {
            if (dist[v] > new_distance) {
                dist[v] = new_distance;
                heap.push(make_pair(-new_distance, v));
            }
        };

        addToQ(source, (T)(0));
        while (!heap.empty()) {
            pair<T, int> pr = heap.top();
            heap.pop();
            int v = pr.second;

            if (processed[v])
                continue;
            processed[v] = true;

            T d = -pr.first;

            for (int i = 0;i < Edges[v].size(); i++) {
                int v2 = Edges[v][i];
                T wt = EdgeWeights[v][i];
                addToQ(v2, dist[v] + wt);
            }
        }

        return dist;
    }

private:
    int N;
    bool weighted;
    bool directed;

    vector<vector<int> > Edges;
    vector<vector<T> > EdgeWeights;
};

// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    cin >> N;
    Graph<int> tree(N, false, false);
    tree.ReadFromStream(cin);
    VEC(int) dist = tree.BFS(1);
    VEC(int) sideA, sideB;
    FOR(i, 1, N + 1)
        if (dist[i] % 2 == 1)
            sideA.push_back(i);
        else
            sideB.push_back(i);

    int rem1 = N / 3 + (N % 3 != 0);
    int rem2 = N / 3 + (N % 3 == 2);

    if (sideA.size() < sideB.size())
        swap(sideA, sideB);

    VEC(int) Perm(N + 1, -1);

    // sideA.size >= sideB.size
    if (sideA.size() >= rem1 + rem2) {
        FOR(i, 0, rem1)
            Perm[sideA[i]] = 3 * i + 1;
        FOR(i, 0, rem2)
            Perm[sideA[rem1 + i]] = 3 * i + 2;
    } else {
        if (sideA.size() >= rem1 && sideB.size() >= rem2) {
            FOR(i, 0, rem1)
                Perm[sideA[i]] = 3 * i + 1;
            FOR(i, 0, rem2)
                Perm[sideB[i]] = 3 * i + 2;
        } else {
            FOR(i, 0, rem2)
                Perm[sideA[i]] = 3 * i + 2;
            FOR(i, 0, rem1)
                Perm[sideB[i]] = 3 * i + 1;
        }
    }

    set<int> assigned;
    FOR(i, 1, N + 1)
        if (Perm[i] >= 0)
            assigned.insert(Perm[i]);

    int s = 1;
    FOR(i, 1, N + 1)
        if (Perm[i] < 0) {
            while (assigned.count(s))
                s++;
            Perm[i] = s++;
        }

    Perm.erase(Perm.begin());
    cout << Perm;
    return 0;
};

Measured memory_bytes: 22384