#pragma region macro
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

namespace std {
template <typename A, typename B>
string to_string(pair<A, B> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for(int i = 0; i < static_cast<int>(v.size()); i++) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for(size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto& x : v) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
};  // namespace std

namespace edamat {
template <class Info>
struct edge {
    int from, to;
    Info info;
    edge(int to, Info info) : to(to), info(info) {}
    edge(int from, int to, Info info) : from(from), to(to), info(info) {}
};

//! graphは基底クラス！使うときはundirected_graphかdirected_graphを使う。
template <class Info>
class graph {
   protected:
    using edge_type = edge<Info>;
    ::std::size_t N;
    ::std::vector<::std::vector<edge_type>> edges;

   public:
    graph(::std::size_t N_) : N(N_), edges(N_) {}
    virtual void add_edge(int x, int y, Info info = static_cast<Info>(1)) = 0;
    const ::std::vector<edge_type>& delta(int v) const {
        assert(v < N);
        return edges[v];
    }
    const ::std::vector<edge_type>& operator[](int v) const {
        return this->delta(v);
    }
    ::std::size_t size() const noexcept { return N; }
};

template <class Info>
class rooted_tree : public graph<Info> {
   private:
    int l;
    int root = -1;
    ::std::vector<int> _depth;
    ::std::vector<::std::vector<int>> par;

   public:
    rooted_tree(::std::size_t N) : graph<Info>(N), _depth(N) {
        l = 0;
        while((1 << l) < N) l++;
        par =
            ::std::vector<::std::vector<int>>(l, ::std::vector<int>(N + 1, -1));
    }
    void add_edge(int x, int y, Info info = static_cast<Info>(1)) {
        this->edges[x].push_back(edge<Info>(x, y, info));
        this->edges[y].push_back(edge<Info>(y, x, info));
    }
    const int parent(int v) {
        assert(root != -1);
        return par[0][v];
    }
    const int depth(int v) {
        assert(root != -1);
        return _depth[v];
    }

   private:
    void dfs1(int v, int p = -1, int d = 0) {
        if(p != -1) par[0][v] = p;
        _depth[v] = d;
        for(auto& e : this->edges[v]) {
            if(e.to == p) continue;
            dfs1(e.to, v, d + 1);
        }
    }
    ::std::pair<Info, int> dfs2(int v, int p) {
        ::std::pair<Info, int> ret(0, v);
        for(auto& e : this->edges[v]) {
            if(e.to == p) continue;
            auto cost = dfs2(e.to, v);
            cost.first += e.info;
            ret = max(ret, cost);
        }
        return ret;
    }

   public:
    void build(int _root = 0) {
        assert(root == -1);
        root = _root;
        dfs1(root, -1, 0);
        for(int i = 0; i < l - 1; ++i) {
            for(int j = 0; j < this->size(); j++) {
                if(par[i][j] == -1)
                    par[i + 1][j] = -1;
                else
                    par[i + 1][j] = par[i][par[i][j]];
            }
        }
    }

    ::std::vector<Info> bfs(int s) {
        const auto INF = ::std::numeric_limits<Info>::max();
        ::std::vector<Info> dist(this->edges.size(), INF);
        ::std::vector<int> b(this->edges.size(), -1);  // 経路復元

        ::std::queue<Info> q;
        q.push(s);
        dist[s] = 0;
        while(!q.empty()) {
            Info v = q.front();
            q.pop();
            for(auto e : this->edges[v]) {
                if(dist[e.to] != INF) continue;
                dist[e.to] = dist[e.from] + e.info;
                b[e.to] = e.from;  // 経路復元
                q.push(e.to);
            }
        };
        return dist;
    }
    int lca(int x, int y) {
        assert(root != -1);
        if(_depth[x] > _depth[y]) ::std::swap(x, y);
        int dif = _depth[y] - _depth[x];
        for(int i = l - 1; i >= 0; i--) {
            if(dif & (1 << i)) {
                y = par[i][y];
            }
        }
        if(x == y) return x;
        for(int i = l - 1; i >= 0; i--) {
            int nx = par[i][x], ny = par[i][y];
            if(nx != ny) {
                x = nx;
                y = ny;
            }
        }
        return par[0][x];
    }
    int depth_dif(int x, int y) {
        assert(root != -1);
        int z = lca(x, y);
        return _depth[x] + _depth[y] - 2 * _depth[z];
    }
    const Info diameter() {
        auto p = dfs2(0, -1);
        auto q = dfs2(p.second, -1);
        return (q.first);
    }
};
}  // namespace edamat

#pragma endregion

void solve() {
    int n;
    std::cin >> n;
    edamat::rooted_tree<int> tree(n);
    rep(i, n - 1) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        tree.add_edge(a, b);
    }
    tree.build();
    int odd = 0, even = 0;
    rep(i, n) {
        (tree.depth(i) % 2 == 0 ? even : odd)++;
    }
    std::vector<bool> used(n + 1, false);
    std::vector<int> ans(n, -1);
    // 片方がn/3以下なら，すべて3の倍数で埋めてしまう
    if(odd <= n / 3) {
        int now = 1;
        rep(i, n) {
            if(tree.depth(i) % 2 == 1) {
                ans[i] = now * 3;
                used[now * 3] = true;
                now++;
            }
        }
    } else if(even <= n / 3) {
        int now = 1;
        rep(i, n) {
            if(tree.depth(i) % 2 == 0) {
                ans[i] = now * 3;
                used[now * 3] = true;
                now++;
            }
        }
    } else {
        // いずれもn/3より大きいなら，1と2をそれぞれに分離してしまう。
        int now1 = 0, now2 = 0;
        rep(i, n) {
            if(tree.depth(i) % 2 == 0 and 3 * now1 + 1 <= n) {
                ans[i] = now1 * 3 + 1;
                used[now1 * 3 + 1] = true;
                now1++;
            } else if(tree.depth(i) % 2 == 1 and 3 * now2 + 2 <= n) {
                ans[i] = now2 * 3 + 2;
                used[now2 * 3 + 2] = true;
                now2++;
            }
        }
    }
    int i = 1;
    rep(now, n) {
        if(ans[now] != -1) {
            continue;
        }
        while(used[i]) i++;
        ans[now] = i;
        used[i] = true;
    }
    rep(i, n) std::cout << ans[i] << " \n"[i == n - 1];
}

int main() {
    // std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 30836