#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
#pragma endregion

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) { return par[0][v]; }
    const int depth(int v) { 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 std::pair<Info, int> diameter() {
        auto p = dfs2(0, -1);
        auto q = dfs2(p.second, -1);
        return q;
    }
};
}  // namespace edamat

void solve() {
    int n;
    std::cin >> n;
    edamat::rooted_tree<int> tree(n);
    rep(i, n - 1) {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        tree.add_edge(a, b);
    }
    int r;
    r = tree.diameter().second;
    // std::cout << r << std::endl;
    tree.build(0);
    std::vector<int> t(n, -100);
    int now1 = 0, now2 = 0;
    rep(i, n) {
        if(tree.depth(i) % 2 == 0) {
            t[i] = -1;
            now1++;
        } else {
            t[i] = -2;
            now2++;
        }
    }
    // std::cout << now1 << " " << now2 << std::endl;
    std::vector<bool> used(n + 1, false);
    if(3 * now1 + 1 <= n) {
        now1 = 1, now2 = 0;
        rep(i, n) {
            if(t[i] == -1 and 3 * now1 <= n) {
                t[i] = now1 * 3;
                used[now1 * 3] = true;
                now1++;
            } else if(t[i] == -2 and 3 * now2 + 2 <= n) {
                t[i] = now2 * 3 + 2;
                used[now2 * 3 + 2] = true;
                now2++;
            }
        }
    } else if(3 * now2 + 2 <= n) {
        now1 = 0, now2 = 1;
        rep(i, n) {
            if(t[i] == -1 and 3 * now1 + 1 <= n) {
                t[i] = now1 * 3 + 1;
                used[now1 * 3 + 1] = true;
                now1++;
            } else if(t[i] == -2 and 3 * now2 <= n) {
                t[i] = now2 * 3;
                used[now2 * 3] = true;
                now2++;
            }
        }
    } else {
        now1 = 0, now2 = 0;
        rep(i, n) {
            if(t[i] == -1 and 3 * now1 + 1 <= n) {
                t[i] = now1 * 3 + 1;
                used[now1 * 3 + 1] = true;
                now1++;
            } else if(t[i] == -2 and 3 * now2 + 2 <= n) {
                t[i] = now2 * 3 + 2;
                used[now2 * 3 + 2] = true;
                now2++;
            }
        }
    }
    std::stack<int> s;
    repeat(i, 1, n + 1) {
        if(!used[i]) s.emplace(i);
    }
    repeat(i, 1, n + 1) {
        if(t[i - 1] < 0) {
            t[i - 1] = s.top();
            s.pop();
        }
    }
    rep(i, n) std::cout << t[i] << " \n"[i == n - 1];
}

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

Measured memory_bytes: 30836