#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define dump(x)
#define debug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

void dfs(const int N, const int root, const int current, const int previous, const int height, vector<vector<int>> const & edges, vector<int> & answer) {
    if (root != current) {
        answer[current] = answer[root] % 2 == 1 ? (height % 2 + 1) : ((height+1) % 2 + 1);
    }
    debug(current);
    debug(answer[current]);
    for (const auto& next : edges[current]) {
        if (next == previous) continue;
        dfs(N, root, next, current, height+1, edges, answer);
    }
}

void solve(long long N, std::vector<long long> a, std::vector<long long> b){
    vector<vector<int>> edges(N+1);
    vector<int> answer(N+1,-1), unusedMin;
    rep(i,0,N-1) {
        edges[a[i]].emplace_back(b[i]);
        edges[b[i]].emplace_back(a[i]);
    }
    unusedMin = {3, 1, 2};
    answer[1] = 1;
    dfs(N, 1, 1, -1, 0, edges, answer);
    vector<int> cnt(3);
    rep(i,1,N+1) cnt[answer[i]]++;
    rep(i,1,N+1) {
        if (N/3 >= cnt[1]) {
            if (answer[i] == 1) {
                answer[i] = unusedMin[0];
                unusedMin[0] += 3;
            } else {
                for (auto j : vector<int>{1,2,0}) {
                    if (unusedMin[j] <= N) {
                        answer[i] = unusedMin[j];
                        unusedMin[j] += 3;
                        break;
                    }
                }
            }
        } else if (N/3 >= cnt[2]) {
            if (answer[i] == 2) {
                answer[i] = unusedMin[0];
                unusedMin[0] += 3;
            } else {
                for (auto j : vector<int>{1,2,0}) {
                    if (unusedMin[j] <= N) {
                        answer[i] = unusedMin[j];
                        unusedMin[j] += 3;
                        break;
                    }
                }
            }
        } else {
            if (answer[i] == 1) {
                for (auto j : vector<int>{1,0}) {
                    if (unusedMin[j] <= N) {
                        answer[i] = unusedMin[j];
                        unusedMin[j] += 3;
                        break;
                    }
                }
            } else {
                for (auto j : vector<int>{2,0}) {
                    if (unusedMin[j] <= N) {
                        answer[i] = unusedMin[j];
                        unusedMin[j] += 3;
                        break;
                    }
                }
            }
        }
    }
    rep(i,1,N+1) {
        cout << answer[i] << (i == N ? "\n" : " ");
    }
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N-1);
    std::vector<long long> b(N-1);
    for(int i = 0 ; i < N-1 ; i++){
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
    }
    solve(N, std::move(a), std::move(b));
    return 0;
}


Measured memory_bytes: 26880