#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

typedef pair<ll, ll> P;
vec d;
struct edge {
    ll to, cost;
};
vector<vector<edge>> G;

void dijkstra (ll s, ll V) {
    priority_queue<P, vector<P>, greater<P>> que;
    d.assign(V, inf);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        ll v = p.second;
        if (d[v] < p.first) continue;
        for (edge e : G[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

vec color;

void dfs (ll v, ll c, ll from) {
    color[v] = c;
    for (auto e : G[v]) {
        if (e.to == from) continue;
        if (color[e.to] == 0) dfs(e.to, -c, v);
    }
    return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;
    G.assign(N, vector<edge>());
    Rep (i, N-1) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back({b, 1});
        G[b].push_back({a, 1});
    }

    color.assign(N, 0);

    dfs(0, 1, -1);
    ll cnt = 0;
    Rep (i, N) {
        if (color[i] == 1) cnt++;
    }

    vec num(N, -1);
    ll zero = N/3, one = (N+2)/3, two = (N+1)/3;
    if (cnt < two) {
        Rep (i, N) {
            if (color[i] == -1) {
                if (one) {
                    num[i] = 1;
                    one--;
                } else if (two) {
                    num[i] = 2;
                    two--;
                } else {
                    num[i] = 0;
                }
            } else {
                num[i] = 0;
            }
        }
    } else if (cnt - two < one) {
        Rep (i, N) {
            if (color[i] == 1) {
                if (two) {
                    num[i] = 2;
                    two--;
                } else {
                    num[i] = 0;
                }
            } else {
                if (one) {
                    num[i] = 1;
                    one--;
                } else {
                    num[i] = 0;
                }
            }
        }
    } else {
        Rep (i, N) {
            if (color[i] == 1) {
                if (two) {
                    num[i] = 2;
                    two--;
                } else if (one) {
                    num[i] =1;
                    one--;
                } else {
                    num[i] = 0;
                }
            } else {
                num[i] = 0;
            }
        }
    }

    // Rep (i, N) {
    //     cout << num[i] << " \n"[i==N-1];
    // }


    ll tmp0 = 3, tmp1 = 1, tmp2 = 2;
    Rep (i, N) {
        if (num[i] == 0) {
            num[i] = tmp0;
            tmp0 += 3;
        } else if (num[i] == 1) {
            num[i] = tmp1;
            tmp1 += 3;
        } else {
            num[i] = tmp2;
            tmp2 += 3;
        }
    }

    Rep (i, N) {
        cout << num[i] << " \n"[i==N-1];
    }
}

Measured memory_bytes: 21504