#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

struct IO {
    static constexpr size_t buf_size = 1 << 18;
    char buf_in[buf_size], buf_out[buf_size];
    size_t pt_in = 0, pt_out = 0, tail_in = 0;
    char strs[10000 * 4];
    inline size_t num_digits(long long x) {
        if(x >= (long long)1e9) {
            if(x >= (long long)1e18) return 19;
            if(x >= (long long)1e17) return 18;
            if(x >= (long long)1e16) return 17;
            if(x >= (long long)1e15) return 16;
            if(x >= (long long)1e14) return 15;
            if(x >= (long long)1e13) return 14;
            if(x >= (long long)1e12) return 13;
            if(x >= (long long)1e11) return 12;
            if(x >= (long long)1e10) return 11;
            return 10;
        } else {
            if(x >= (long long)1e8) return 9;
            if(x >= (long long)1e7) return 8;
            if(x >= (long long)1e6) return 7;
            if(x >= (long long)1e5) return 6;
            if(x >= (long long)1e4) return 5;
            if(x >= (long long)1e3) return 4;
            if(x >= (long long)1e2) return 3;
            if(x >= (long long)1e1) return 2;
            return 1;
        }
    }
    IO() {
        load();
        for(int i = 0; i < 10000; ++i) {
            int j = i;
            for(int t = 3; t >= 0; --t) {
                strs[i * 4 + t] = j % 10 + '0';
                j /= 10;
            }
        }
    }
    ~IO() { flush(); }
    inline void load() {
        memcpy(buf_in, buf_in + pt_in, tail_in - pt_in);
        size_t width = tail_in - pt_in;
        tail_in = width + fread(buf_in + width, 1, buf_size - width, stdin);
        pt_in = 0;
    }
    inline void flush() {
        fwrite(buf_out, 1, pt_out, stdout);
        pt_out = 0;
    }
    inline void read(char& c) { c = buf_in[pt_in++]; }
    template <class T>
    inline void read(T& x) {
        if(pt_in + 32 > tail_in) load();
        char c;
        do {
            read(c);
        } while(c < '0');
        bool minus = 0;
        if(c == '-') {
            minus = 1;
            read(c);
        }
        x = 0;
        while(c >= '0') {
            x = x * 10 + (c & 15);
            read(c);
        }
        if(minus) x = -x;
    }
    inline void write(char c) { buf_out[pt_out++] = c; }
    template <class T>
    inline void write(T x) {
        if(pt_out > buf_size - 32) flush();
        if(x < 0) {
            write('-');
            x = -x;
        }
        size_t digits = num_digits(x);
        int i;
        for(i = pt_out + digits - 4; i > (int)pt_out; i -= 4) {
            memcpy(buf_out + i, strs + (x % 10000) * 4, 4);
            x /= 10000;
        }
        memcpy(buf_out + pt_out, strs + x * 4 + (pt_out - i), 4 + i - pt_out);
        pt_out += digits;
    }
    inline void write(const char* s) {
        if(pt_out > buf_size - 32) flush();
        for(int i = 0; s[i] != 0; ++i) write(s[i]);
    }
    template <class T>
    inline void writeln(T x) {
        write(x);
        write('\n');
    }
} io;

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

#pragma endregion

void solve() {
    int n;
    io.read(n);
    edamat::rooted_tree<int> tree(n);
    rep(i, n - 1) {
        int a, b;
        io.read(a);
        io.read(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) {
        io.write(t[i]);
        io.write(" \n"[i == n - 1]);
    }
}

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

Measured memory_bytes: 32372