#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

vector<vector<int> > g;  // to
vector<int> depth;

void dfs(int par, int curr, int depth_curr)
{
    depth[curr] = depth_curr;
    int i;
    for (i = 0; i < (int)g[curr].size(); i++) {
        int next = g[curr][i];
        if (par == next) continue;
        dfs(curr, next, depth_curr+1);
    }
       
    return;
}

void solve()
{
    int n;
    scanf("%d", &n);
    g.resize(n);
    depth.resize(n);
    int i;
    for (i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b); a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(-1, 0, 0);

    vector<vector<int> > z(n);
    for (i = 0; i < n; i++) {
        z[depth[i]].push_back(i);
    }

    int cnt[2] = { 0 };
    for (i = 0; i < n; i++) {
        int num0=(int)z[i].size();
        cnt[i % 2] += num0;
    }

    int cntans[3] = { n / 3,n / 3,n / 3 };
    for (i = 0; i < (n % 3); i++) {
        cntans[i]++;
    }

    int large = 0, small = 1;
    if (cnt[0] < cnt[1]) {
        large = 1; small = 0;
    }
    vector<int> ans(n);
    int j;
    if (cnt[small] >= cntans[1]) {
        int curr1 = 1, curr2 = 2, curr0 = 3;
        for (i = 0; i < n; i++) {
            for (j = 0; j < (int)z[i].size(); j++) {
                int tmp=z[i][j];
                if (i % 2 == large) {
                    if (curr1 <= n) {
                        ans[tmp] = curr1;
                        curr1 += 3;
                    }
                    else {
                        ans[tmp] = curr0;
                        curr0 += 3;
                    }
                }
                else {
                    if (curr2 <= n) {
                        ans[tmp] = curr2;
                        curr2 += 3;
                    }
                    else {
                        ans[tmp] = curr0;
                        curr0 += 3;
                    }
                }
            }
        }
    }
    else {
        int curr1 = 1, curr2 = 2, curr0 = 3;
        for (i = 0; i < n; i++) {
            for (j = 0; j < (int)z[i].size(); j++) {
                int tmp = z[i][j];
                if (i % 2 == small) {
                    ans[tmp] = curr0;
                    curr0 += 3;
                }
                else {
                    if (curr1 <= n) {
                        ans[tmp] = curr1;
                        curr1 += 3;
                    }
                    else if (curr2 <= n) {
                        ans[tmp] = curr2;
                        curr2 += 3;
                    }
                    else {
                        ans[tmp] = curr0;
                        curr0 += 3;
                    }
                }
            }
        }
    }
    for (i = 0; i < n; i++) {
        printf("%d", ans[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T; scanf("%d", &T);
    while(T--) {
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 26240