#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144 * 4LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}


#define int ll

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

vector<int> vertexs[500000];
int dist[500000];
void dfs(int now, int back) {
    for (auto x : vertexs[now]) {
        if (x == back) continue;
        dist[x] = dist[now] + 1;
        dfs(x, now);
    }
}

int ans[500000];

void solve() {
    int n;
    cin >> n;
    REP(i, n-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        vertexs[a].push_back(b);
        vertexs[b].push_back(a);
    }
    REP(i, n) {
        if (vertexs[i].size() == 1) {
            dfs(i, -1);
            int cnt[2] = {};
            REP(q, n) {
                cnt[dist[q] % 2]++;
            }
            int cnter[2] = { (n + 2) / 3,(n + 1) / 3 };
            if (cnt[0] >= cnter[0] && cnt[1] >= cnter[1]) {
                //適当配色
                int itr[3] = { 1,2,3 };
                REP(q, n) {
                    if (dist[q] % 2 == 0) {
                        if (cnt[0] > cnter[0]) {
                            cnt[0]--;
                            ans[q] = itr[2];
                            itr[2] += 3;
                        }
                        else {
                            ans[q] = itr[0];
                            itr[0] += 3;
                        }
                    }
                    else {
                        if (cnt[1] > cnter[1]) {
                            cnt[1]--;
                            ans[q] = itr[2];
                            itr[2] += 3;
                        }
                        else {
                            ans[q] = itr[1];
                            itr[1] += 3;
                        }
                    }
                }
            }
            else {
                //少ない方を3にする
                int target = 0;
                int itr[3] = { 1,2,3 };
                if (cnt[0] > cnt[1]) target = 1;
                REP(q, n) {
                    if (dist[q] % 2 == target) {
                        ans[q] = itr[2];
                        itr[2] += 3;
                    }
                }
                REP(q, n) {
                    if (ans[q] != 0) continue;
                    REP(j, 3) {
                        if (itr[j] <= n) {
                            ans[q] = itr[j];
                            itr[j] += 3;
                            break;
                        }
                    }
                }
            }

            REP(i, n) {
                cout << ans[i] << " ";
            }
            cout << endl;
            return;
        }
    }
}

#undef int
int main() {
    init();
    solve();
}


Measured memory_bytes: 31872