// #pragma GCC optimize("Ofast")

// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>

using namespace std;

template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}

template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define left left228
#define right right228
#define ld long double
#define list list228
// #define prev prev228
#define mp make_pair
#define list list228
#define all(v) v.begin(), v.end()

const int N = 228228;

vector<int> g[N];
vector<int> even, odd;

void dfs(int v, int par = 0, int h = 0) {
    if (h & 1) odd.emplace_back(v);
    else even.emplace_back(v);
    for (int to : g[v]) {
        if (to != par) {
            dfs(to, v, h + 1);
        }
    }
}
int p[N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dfs(1);
    int size_even = (int)even.size();
    int size_odd = (int)odd.size();
    int one = 0, two = 0, zero = 0;
    vector<int> ones, twos, zeroes;
    for (int i = 1; i <= n; ++i) {
        if (i % 3 == 1) {
            ++one;
            ones.emplace_back(i);
        }
        if (i % 3 == 2) {
            ++two;
            twos.emplace_back(i);
        }
        if (i % 3 == 0) {
            ++zero;
            zeroes.emplace_back(i);
        }
    }
    if (size_even >= one && size_odd >= two) {
        for (int i = 0; i < one; ++i) {
            p[even[i]] = ones[i];
        }
        for (int i = one; i < size_even; ++i) {
            p[even[i]] = zeroes.back();
            zeroes.pop_back();
        }
        for (int i = 0; i < two; ++i) {
            p[odd[i]] = twos[i];
        }
        for (int i = two; i < size_odd; ++i) {
            p[odd[i]] = zeroes.back();
            zeroes.pop_back();
        }
    } else if (size_even >= two && size_odd >= one) {
        for (int i = 0; i < two; ++i) {
            p[even[i]] = twos[i];
        }
        for (int i = two; i < size_even; ++i) {
            p[even[i]] = zeroes.back();
            zeroes.pop_back();
        }
        for (int i = 0; i < one; ++i) {
            p[odd[i]] = ones[i];
        }
        for (int i = one; i < size_odd; ++i) {
            p[odd[i]] = zeroes.back();
            zeroes.pop_back();
        }
    } else {
        if (size_even < size_odd) {
            for (int i : even) {
                p[i] = zeroes.back(); zeroes.pop_back();
            }
            for (int i : odd) {
                if (!ones.empty()) {
                    p[i] = ones.back(); ones.pop_back();
                } else if (!twos.empty()) {
                    p[i] = twos.back(); twos.pop_back();
                } else {
                    p[i] = zeroes.back(); zeroes.pop_back();
                }
            }
        } else {
            for (int i : odd) {
                p[i] = zeroes.back(); zeroes.pop_back();
            }
            for (int i : even) {
                if (!ones.empty()) {
                    p[i] = ones.back(); ones.pop_back();
                } else if (!twos.empty()) {
                    p[i] = twos.back(); twos.pop_back();
                } else {
                    p[i] = zeroes.back(); zeroes.pop_back();
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << p[i] << ' ';
    }
    cout << '\n';
    return 0;
}

/*
3
1 1 2
2 2 2
3 3 2
2 1 1
3 2 1


2 2
1 1 2
2 2 2
1 2 3
2 1 1

2
2 1 2 2 3
2 2 2 1 1

бархатом обитый гроб
5
1 2
2 3
3 4
3 5
1
2 3
1 2
4 3
2 3 5

*/




Measured memory_bytes: 25068