#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class UnionFind {
    vector<int> p;//p[i]はiの属する組織
    vector<int> sz;

public:
    UnionFind(int n) {
        p.resize(n);
        sz.resize(n);

        for (int i = 0; i < n; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }

/* xの属する集合を返す */
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

/* yにxを統合する */
    void unite(int x, int y) {
        sz[find(y)] += sz[find(x)];
        sz[find(x)] = 0;
        p[find(x)] = p[find(y)];
    }

/* xとyが属する集合が同じかを判定する */
    bool same(int x, int y) {
        return find(x) == find(y);
    }

/* xに属する集合のサイズを求める */
    int size(int x) {
        return sz[find(x)];
    }
};

class Solve {
public:

    void solve(vector<vector<Int>> tree) {
        Int n = tree.size();
//        Int n;
//        cin >> n;
//        vector<vector<Int>> tree(n);
//        for (int i = 1; i < n; ++i) {
//            Int a, b;
//            cin >> a >> b;
//            a--, b--;
//            tree[a].push_back(b);
//            tree[b].push_back(a);
//        }

        vector<Int> color(n, -1);
        vector<Int> pal(2);

        auto dfs = [&](auto self, Int v, Int c = 0, Int p = -1) -> void {
            color[v] = c;
            pal[c]++;
            for (auto e : tree[v]) {
                if (e != p) {
                    self(self, e, 1 - c, v);
                }
            }
        };

        dfs(dfs, 0);

        vector<vector<Int>> md(3);
        for (int i = n; i >= 1; --i) {
            md[i % 3].push_back(i);
        }

        vector<Int> ans(n);

//        if (md[0].size() + md[1].size() > pal[0] || md[0].size() + md[2].size() > pal[0]) {
        if (md[0].size() >= pal[0]) {
            //colorが0のやつをすべて3でぬる
            for (int i = 0; i < n; ++i) {
                if (color[i] == 0) {
                    if (md[0].size() == 0) exit(-1);
                    ans[i] = md[0].back();
                    md[0].pop_back();
                } else {
                    if (md[1].size()) {
                        ans[i] = md[1].back();
                        md[1].pop_back();
                    } else if (md[2].size()) {
                        ans[i] = md[2].back();
                        md[2].pop_back();
                    } else {
                        ans[i] = md[0].back();
                        md[0].pop_back();
                    }
                }
            }
//        } else if (md[0].size() + md[1].size() > pal[1] || md[0].size() + md[2].size() > pal[1]) {
        } else if (md[0].size() >= pal[1]) {
            for (int i = 0; i < n; ++i) {
                if (color[i] == 1) {
                    if (md[0].size() == 0) exit(-1);
                    ans[i] = md[0].back();
                    md[0].pop_back();
                } else {
                    if (md[1].size()) {
                        ans[i] = md[1].back();
                        md[1].pop_back();
                    } else if (md[2].size()) {
                        ans[i] = md[2].back();
                        md[2].pop_back();
                    } else {
                        ans[i] = md[0].back();
                        md[0].pop_back();
                    }
                }
            }
        } else {
            for (int i = 0; i < n; ++i) {
                if (color[i] == 0) {
                    if (md[1].size() == 0) {
                        if (md[0].size() == 0) exit(-1);

                        ans[i] = md[0].back();
                        md[0].pop_back();
                    } else {
                        ans[i] = md[1].back();
                        md[1].pop_back();
                    }
                } else {
                    if (md[2].size() == 0) {
                        if (md[0].size() == 0) exit(-1);

                        ans[i] = md[0].back();
                        md[0].pop_back();
                    } else {
                        ans[i] = md[2].back();
                        md[2].pop_back();
                    }

                }
            }
        }
        for (auto e : ans) {
            cout << e << " ";
        }

        cout << endl;

    }


    bool bf(vector<vector<Int>> &tree) {
        vector<Int> p(tree.size());
        iota(all(p), 1);
        do {
            vector<vector<Int>> dist(p.size(), vector<Int>(p.size(), INFl));
            for (int i = 0; i < p.size(); ++i) dist[i][i] = 0;
            for (int i = 0; i < tree.size(); ++i) {
                for (auto e : tree[i]) {
                    dist[i][e] = 1;
                }
            }

            for (int k = 0; k < tree.size(); ++k) {
                for (int i = 0; i < tree.size(); ++i) {
                    for (int j = 0; j < tree.size(); ++j) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
            bool flag = true;
            for (int i = 0; i < tree.size(); ++i) {
                for (int j = 0; j < tree.size(); ++j) {
                    if (dist[i][j] == 3) {
                        if (!(p[i] * p[j] % 3 == 0 || (p[i] + p[j]) % 3 == 0)) {
                            flag = false;
                        }
                    }
                }
            }
            if (flag) {
                for (auto e : p) {
                    cout << e << " ";
                }
                cout << endl;
                return true;
            }


        } while (next_permutation(all(p)));
        cout << -1 << endl;
        return false;

    }
};

vector<vector<Int>> make_tree(Int n) {
    UnionFind uf(n);
    vector<pair<Int, Int>> edge;
    for (int i = 0; i + 1 < n; ++i) {
        Int a = rand() % n;
        Int b = rand() % n;
        while (uf.same(a, b)) {
            a = rand() % n;
            b = rand() % n;
        }
        uf.unite(a, b);
        edge.emplace_back(a, b);
    }
    vector<vector<Int>> ret(n);
    cout << n << endl;
    for (auto e : edge) {
        Int a = e.first;
        Int b = e.second;
        ret[a].push_back(b);
        ret[b].push_back(a);

        cout << a + 1 << " " << b + 1 << endl;
    }
    return ret;
}

vector<vector<Int>> inp_tree() {
    Int n;
    cin >> n;
    vector<vector<Int>> ret(n);
    for (int i = 1; i < n; ++i) {
        Int a, b;
        cin >> a >> b;
        a--, b--;
        ret[a].push_back(b);
        ret[b].push_back(a);
    }

    return ret;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);


    auto tree = inp_tree();
    Solve().solve(tree);

//    while (true) {
//        Int n = rand() % 10 + 1;
//        auto tree = make_tree(n);
//        Solve().solve(tree);
//    }



//    while (true) {
////        Int n = rand() % 10;
////        auto tree = make_tree(10);
//        auto tree = inp_tree();
//        if (!Solve().bf(tree)) {
//            break;
//        }
//        cout << "-----------" << endl;
//    }


    return 0;
}


Measured memory_bytes: 33648