//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//typedef tree < int , null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> TREE;
#define ll long long
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define pss pair<short,short>
#define pld pair<long double,long double >
#define ld long double
#define piii  pair<pii,int>
#define vii vector<pair<int,int> >
#define st first
#define nd second
#define pll pair<ll,ll>
#define speed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define M_PI 3.14159265358979323846
//#define int long long
const int mod=1000000007;
//const int mod=1009;
//const int mod=998244353;
const int inf=1000000009;
const long long INF=1000000000000000009;
const long long big=1000000000000000;
const long double eps=0.000000000000000000001;
using namespace std;
int L[200005],D[3],K[200005],N[2];
vi P[200005];
vi W[200009];
void dfs(int n,int p)
{
    N[L[n]%2]++;
    W[L[n]].pb(n);
    for(auto v:P[n])
    {
        if(v!=p)
        {
            L[v]=L[n]+1;
            dfs(v,n);
        }
    }
}
int main()
{
    speed
    int n;
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int a,b;
        cin>>a>>b;
        P[a].pb(b);
        P[b].pb(a);
    }
    for(int i=1; i<=n; i++)
        D[i%3]++,K[i]=-1;
    dfs(1,0);
    int skad,s;
    if(N[0]<=N[1])
    {
        skad=0;
        s=N[0];
    }
    else
    {
        skad=1;
        s=N[1];
    }
    int ile=D[1];
    for(int i=200000+skad; i>=0; i-=2)
    {
        for(auto v:W[i])
        {
            if(ile)
                K[v]=1,ile--;
        }

    }
    if(ile>0)
    {
        //cout<<ile<<endl;
        for(int i=200000+skad+1; i>=0; i-=2)
        {
            int x=0,y=W[i+3].size(),z=W[i+1].size(),t;
            if(i>=3)
                x=W[i-3].size();
            if(i>=1)
                t=W[i-1].size();
            if(W[i].size()>x+y+z+t&&ile)
            {
                ile+=x+y+z+t;
                //  cout<<i<<endl;
                if(i>=3)
                {
                    for(auto v:W[i-3])
                        K[v]=0;
                    W[i-3].clear();
                }
                if(i>=1)
                {
                    for(auto v:W[i-1])
                        K[v]=0;
                    W[i-1].clear();
                }
                for(auto v:W[i+1])
                    K[v]=0;
                W[i+1].clear();
                for(auto v:W[i+3])
                    K[v]=0;
                W[i+3].clear();
                while(!W[i].empty()&&ile)
                {
                    K[W[i].back()]=1;
                    W[i].pop_back();
                    ile--;
                }
            }
        }
    }
    int ile2=D[2];
    for(int i=(skad+1)%2; i<=n; i+=2)
    {
        while(!W[i].empty()&&ile2)
        {
            K[W[i].back()]=2;
            W[i].pop_back();
            ile2--;
        }
    }
    int l0=3,l1=1,l2=2;
    while(ile||ile2)
    {
        continue;
    }
    for(int i=1; i<=n; i++)
    {
        if(K[i]<=0)
        {
            cout<<l0<<" ";
            l0+=3;
        }
        else if(K[i]==1)
        {
            cout<<l1<<" ";
            l1+=3;
        }
        else
        {
            cout<<l2<<" ";
            l2+=3;
        }
    }
    return 0;
}


Measured memory_bytes: 28672