#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC omodtimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
typedef complex<long double> com;
 
const ll mod = 1e9+7;

vector <vector<ll>> graph;
vector <ll> ans;
vector <ll> color;
set <ll> num0;
set <ll> num1;
set <ll> num2;
ll k1 = 0,k2 = 0;

void dfs(ll u,ll p = 0,ll d = 0){
    if (d & 1){
        color[u] = 0;
        k1++;
        if (num1.size() > 0){
            ans[u] = *(num1.begin());
            num1.erase(num1.begin());
        }
        else if (num0.size() > 0){
            ans[u] = *(num0.begin());
            num0.erase(num0.begin());
        }
        else {
            ans[u] = *(num2.begin());
            num2.erase(num2.begin());
        }
    }
    else {
        color[u] = 1;
        k2++;
        if (num2.size() > 0){
            ans[u] = *(num2.begin());
            num2.erase(num2.begin());
        }
        else if (num0.size() > 0){
            ans[u] = *(num0.begin());
            num0.erase(num0.begin());
        } else {    
            ans[u] = *(num1.begin());
            num1.erase(num1.begin());
        }
    }
    for (int z=0;z<graph[u].size();z++){
        if (graph[u][z] == p) continue;
        dfs(graph[u][z],u,d+1);
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll n;
    cin >> n;
    ans.resize(n+1);
    for (int z=1;z<=n;z++){
        if (z % 3 == 0) num0.insert(z);
        else if (z % 3 == 1) num1.insert(z);
        else num2.insert(z);
    }
    graph.resize(n+1);
    color.resize(n+1);
    for (int z=0;z<n-1;z++){
        ll u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1);
    for (int z=1;z<=n;z++){
        if (z % 3 == 0) num0.insert(z);
        else if (z % 3 == 1) num1.insert(z);
        else num2.insert(z);
    }
    if (k1 <= n/3){
        for (int z=1;z<=n;z++){
            if (color[z] == 0){
                ans[z] = *(num0.begin());
                num0.erase(num0.begin());
            } else {
                 if (num1.size() > 0){
                    ans[z] = *(num1.begin());
                    num1.erase(num1.begin());
                }
                else if (num2.size() > 0){
                    ans[z] = *(num2.begin());
                    num2.erase(num2.begin());
                }
                else {
                    ans[z] = *(num0.begin());
                    num0.erase(num0.begin());
                }
            }
        }
    }
    else if (k2 <= n/3){
        for (int z=1;z<=n;z++){
            if (color[z] == 1){
                ans[z] = *(num0.begin());
                num0.erase(num0.begin());
            } else {
                if (num1.size() > 0){
                    ans[z] = *(num1.begin());
                    num1.erase(num1.begin());
                }
                else if (num2.size() > 0){
                    ans[z] = *(num2.begin());
                    num2.erase(num2.begin());
                }
                else {
                    ans[z] = *(num0.begin());
                    num0.erase(num0.begin());
                }
            }
        }
    }
    for (int z=1;z<=n;z++){
        cout << ans[z] << " ";
    } cout << endl;
}


Measured memory_bytes: 26728