#include <bits/stdc++.h>


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = rbegin(s); i != rend(s); ++i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.ne(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<typename A, int N, typename T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

int n;
int a[200005], b[200005];
int color[200005];
vector<int> g[200005];
vector<int> cnt[5];
int ans[200005];
void dfs(int pos) {
    rep(i, g[pos].size()) {
        auto v = g[pos][i];
        if (color[v] == -1) {
            color[v] = (color[pos] + 1) % 2;
            dfs(v);
        }
    }
}

void solve() {
    cin >> n;
    rep(i, n - 1) {
        cin >> a[i] >> b[i]; --a[i]; --b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    fillArray(color, -1);
    color[0] = 0;
    dfs(0);
    rep(i, n) cnt[color[i]].push_back(i);

    if (cnt[0].size() < cnt[1].size()) swap(cnt[0], cnt[1]);

    int one = 1, two = 2, three = 3;
    if (cnt[0].size() * 3 >= n && cnt[1].size() * 3 >= n) {
        rep(i, cnt[0].size()) {
            int v = cnt[0][i];
            if (one <= n) {
                ans[v] = one;
                one += 3;
            }
            else {
                ans[v] = three;
                three += 3;
            }
        }

        rep(i, cnt[1].size()) {
            int v = cnt[1][i];
            if (two <= n) {
                ans[v] = two;
                two += 3;
            }
            else {
                ans[v] = three;
                three += 3;
            }
        }
    }
    else {
        rep(i, cnt[1].size()) {
            int v = cnt[1][i];
            ans[v] = three;
            three += 3;
        }

        rep(i, cnt[0].size()) {
            int v = cnt[0][i];
            if (three <= n) {
                ans[v] = three;
                three += 3;
            }
            else if (one <= n) {
                ans[v] = one;
                one += 3;
            }
            else {
                ans[v] = two;
                two += 3;
            }
        }
    }

    rep(i, n) cout << ans[i] << " ";
    cout << endn;

}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 21236