#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007ll
#define D 100000000000000ll
#define B 998244353ll
#define C 8000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

const ll MAXN=200005;
ve<ve<ll>> adj(MAXN);
bool vis[MAXN],par[MAXN];

void dfs(ll v, bool b)
{
    vis[v]=true;
    par[v]=b;
    for(auto i=adj[v].begin();i!=adj[v].end();i++)
        if(!vis[*i])
            dfs(*i,!b);
    return;
}

int main() 
{
    FAST;
    ll n,a,b,c;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,0);
    a=1;
    b=2;
    c=3;
    ll ans[n+1];
    ll c1=0,c2=0;
    for(int i=1;i<=n;i++)
        if(par[i])
            c1++;
        else
            c2++;
    if(c1>n/3 && c2>n/3)
    {
        for(int i=1;i<=n;i++)
            if(par[i])
            {
                if(a<=n)
                {
                    ans[i]=a;
                    a=a+3;
                }
                else
                {
                    ans[i]=c;
                    c+=3;
                }
            }
            else
            {
                if(b<=n)
                {
                    ans[i]=b;
                    b+=3;
                }
                else
                {
                    ans[i]=c;
                    c+=3;
                }
            }
    }
    else
    {
        if(c1<=n/3)
            for(int i=1;i<=n;i++)
                if(par[i])
                {
                    ans[i]=c;
                    c+=3;
                }
                else
                {
                    if(b<=n)
                    {
                        ans[i]=b;
                        b+=3;
                    }
                    else
                    {
                        if(a<=n)
                        {
                            ans[i]=a;
                            a+=3;
                        }
                        else
                        {
                            ans[i]=c;
                            c+=3;
                        }
                    }
                }
        else
            for(int i=1;i<=n;i++)
                if(!par[i])
                {
                    ans[i]=c;
                    c+=3;
                }
                else
                {
                    if(b<=n)
                    {
                        ans[i]=b;
                        b+=3;
                    }
                    else
                    {
                        if(a<=n)
                        {
                            ans[i]=a;
                            a+=3;
                        }
                        else
                        {
                            ans[i]=c;
                            c+=3;
                        }
                    }
                }
    }
    for(int i=1;i<=n;i++)
       cout<<ans[i]<<' ';
    subt;
    return 0;
}

Measured memory_bytes: 16360