#include <bits/stdc++.h>

using namespace std;
using llong = long long int;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

const static int MOD = 1000000007;
const static int IINF = INT_MAX;
const static llong LINF = LLONG_MAX;
const static int dx[4] = {1, 0, -1, 0};
const static int dy[4] = {0, 1, 0, -1};

/* --------------- template start --------------- */
template <typename T> 
struct BinaryIndexTree { // [1, n]
    vector<T> array;
    int n;

    BinaryIndexTree(int _n) {
        array.resize(_n + 1, 0);
        n = _n;
    }

    T cumsum(int i) {
        T s = 0;
        while(i > 0) {
            s += array[i];
            i -= i & -i;
        }

        return s;
    }

    T sum(int i, int j) {
        T ret_i = cumsum(i - 1);
        T ret_j = cumsum(j);

        return ret_j - ret_i;
    }

    void add(int i, T x) {
        while (i <= n) {
            array[i] += x;
            i += i & -i;
        }
    }
};

template<typename T>
struct UnionFind {
    vector<int> par;
    vector<T> sz;

    UnionFind(int n) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_root(int x) {
        return par[x] == x ? x : par[x] = find_root(par[x]);
    }

    bool same(int x, int y) {
        return find_root(x) == find_root(y);
    }

    void unite(int x, int y) {
        x = find_root(x);
        y = find_root(y);
        if (x == y) return;
        
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
    }

    T size_of_tree(int x) {
        return sz[find_root(x)];
    }
};
/* --------------- template end --------------- */

/* --------------- function start --------------- */
llong my_gcd(llong a, llong b) {
    return (a ? my_gcd(b % a, a) : b);
}
llong my_lcm(llong a, llong b) {
    return a * b / my_gcd(a, b);    
}

llong facmod(llong n) {
    if (n == 0) return 1;

    llong res = n;
    for (int i = n - 1; i > 0; --i) {
        res = (res * i) % MOD;
    }

    return res;
}
llong powmod(llong a, llong n) {
    llong res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }

    return res;
}
llong modinv(llong n) {
    return powmod(n, MOD - 2);
}
llong combmod(llong n, llong k) {
    llong res = 1;
    for (int i = 0; i < k; ++i) {
        res = (res * (n - i)) % MOD;
    }
    res = (res * modinv(facmod(k))) % MOD;

    return res;
}
/* --------------- function end --------------- */

vector<vector<int> > G;
vector<int> red, black; // red : odd, black : even
vector<bool> visited;

void dfs(int vertex, int depth) {
    if (visited[vertex]) return;
    else visited[vertex] = true;

    if (depth % 2 == 0) black.push_back(vertex);
    else red.push_back(vertex);

    rep(i, (int)G[vertex].size()) dfs(G[vertex][i], depth + 1);
}

int main(int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    G.resize(n);

    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    visited.resize(n, false);
    dfs(0, 0);
    /*
    cout << "black" << endl;
    rep(i, (int)black.size()) cout << black[i] << " ";
    cout << endl;
    rep(i, (int)red.size()) cout << red[i] << " ";
    cout << endl; */
    vector<int> P(n, -1);
    if ((int)red.size() > n / 3 && (int)black.size() > n / 3) {
        for (int i = 0; i <= (n - 1) / 3; ++i) P[red[i]] = 3 * i + 1;
        /* rep(i, n) cout << P[i] << " ";
        cout << endl; */
        for (int i = 0; i <= (n - 2) / 3; ++i) P[black[i]] = 3 * i + 2;
        int k = 1;
        rep(i, n) if (P[i] == -1) P[i] = 3 * k, ++k;
    } else {
        if ((int)red.size() <= n / 3) {
            for (int i = 1; i <= n / 3; ++i) {
                if (i <= (int)red.size()) P[red[i - 1]] = 3 * i;
                else P[black[i - (int)red.size() - 1]] = 3 * i;
            }
        } else {
            for (int i = 1; i <= n / 3; ++i) {
                if (i <= (int)black.size()) P[black[i - 1]] = 3 * i;
                else P[red[i - (int)black.size() - 1]] = 3 * i  ;
            }
        }
        int cnt = 0;
        rep(i, n) {
            if (P[i] == -1) {
                if (cnt % 2 == 0) P[i] = 3 * (cnt / 2) + 1;
                else P[i] = 3 * (cnt / 2) + 2;
                ++cnt;
            }
        }
    }

    rep(i, n) {
        cout << P[i];
        if (i == n - 1) cout << endl;
        else cout << ' ';
    }

    return 0;
} 

Measured memory_bytes: 18164