/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int n;
vector<vector<int>> g;
vector<int> c;
int cnt[2] = {0};
void dfs(int now, int p, int d){
    c[now] = d % 2;
    cnt[d % 2]++;
    rep(i, g[now].size()){
        int next = g[now][i];
        if(next == p){
            continue;
        }
        dfs(next, now, d + 1);
    }
}
void out(vector<int> ans){
    rep(i, ans.size()){
        cout << ans[i] << " ";
    }
    cout << endl;
}
int main(void){
    cin >> n;
    g.resize(n);
    c.resize(n);
    rep(i, n - 1){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(0, -1, 0);
    vector<int> ans(n, 0);
    vector<int> mod1;
    vector<int> mod2;
    vector<int> mod0;
    //cout << "h" << endl;
    for(int i = 1; i <= n; i++){
        if(i % 3 == 1){
            mod1.push_back(i);
        } else if(i % 3 == 2){
            mod2.push_back(i);
        } else {
            mod0.push_back(i);
        }
    }

    //cout << cnt[0] << " " << cnt[1] << endl;

    if(cnt[0] > n / 3 && cnt[1] > n / 3){
        rep(i, n){
            if(c[i]){
                if(mod1.size() > 0){
                    ans[i] = mod1.back();
                    mod1.pop_back();
                } else {
                    ans[i] = mod0.back();
                    mod0.pop_back();
                }
 
            } else {
                if(mod2.size() > 0){
                    ans[i] = mod2.back();
                    mod2.pop_back();
                } else {
                    ans[i] = mod0.back();
                    mod0.pop_back();
                }
            }
        }
        out(ans);
    } else if(cnt[0] <= n / 3){
        vector<int> mod12;
        rep(i, mod1.size()) mod12.push_back(mod1[i]);
        rep(i, mod2.size()) mod12.push_back(mod2[i]);
        rep(i, n){
            if(c[i] == 0){
                ans[i] = mod0.back();
                mod0.pop_back();
            } else {
                if(mod12.size() > 0){
                    ans[i] = mod12.back();
                    mod12.pop_back();
                } else {
                    ans[i] = mod0.back();
                    mod0.pop_back();
                }

            }
        }
        out(ans);
    } else if(cnt[1] <= n / 3){
        vector<int> mod12;
        rep(i, mod1.size()) mod12.push_back(mod1[i]);
        rep(i, mod2.size()) mod12.push_back(mod2[i]);
        rep(i, n){
            
            if(c[i] == 1){
                ans[i] = mod0.back();
                mod0.pop_back();
            } else {
                if(mod12.size() > 0){
                    ans[i] = mod12.back();
                    mod12.pop_back();
                } else {
                    ans[i] = mod0.back();
                    mod0.pop_back();
                }
            }
        }
        out(ans);
    } else {
        cout << -1 << endl;
    }
}   

Measured memory_bytes: 19320