#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b) {
    if (b==0) return 1;
    ll c = power(a,b>>1);
    c = (c*c)%mod;
    if (b&1) return (c*a)%mod;
    return c;
}
ll powerwithoutmod(ll a,ll b) {
    if (b==0) return 1;
    ll c = powerwithoutmod(a,b>>1);
    c = (c*c);
    if (b&1) return (c*a);
    return c;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)2e5+5;
const int Q = 301;
const int logN = 16;

vector<int> v[N], temp[2];
int cnt[2];
void dfs(int i,int p,int num) {
    cnt[num]++;
    temp[num].pb(i);
    for (auto it:v[i]) {
        if (it!=p) {
            dfs(it,i,1-num);
        }
    }
}
void solve() {
    int n,x,y;
    cin>>n;
    vector<int> ans(n+1,-1), rem = {n/3,(n+2)/3,(n+1)/3}, nxt = {3,1,2};
    REP(i,1,n-1) {
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,1,0);
    int i = (cnt[0]<=cnt[1]) ? 0 : 1;
    if (min(cnt[0],cnt[1])<=n/3) {
        for (auto it:temp[i]) {
            ans[it] = 0;
            rem[0]--;
        }
    }
    else {
        for (auto it:temp[i]) {
            if (rem[1]>0) {
                ans[it] = 1;
                rem[1]--;
            }
            else {
                ans[it] = 0;
                rem[0]--;
            }
        }
    }
    REP(i,1,n) {
        if (ans[i]==(-1)) {
            REP(k,0,2) {
                if (rem[k]>0) {
                    ans[i] = k;
                    rem[k]--;
                    break;
                }
            }
        }
        cout<<nxt[ans[i]]<<" ";
        nxt[ans[i]] += 3;
    }
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        cout<<"\n";
    }
}


Measured memory_bytes: 21620