/*
               ██████  ██████
               ██   ██ ██   ██
 Author ->     ██████  ██   ██
               ██      ██   ██
               ██      ██████
 
        nik is love.
        nik is motivation.
        Ek modulus aapki jindagi barbaad kar sakti hai
        Watch for integer overflows.
        A dream doesn't become reality through magic; it takes sweat, determination and hard work" — Colin Powell
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional>
#define mp                    make_pair
#define pb                    push_back
#define ll                    long long
#define ss                       second
#define ff                        first
#define fr(i,a,b)   for(ll i=a;i<b;i++)
#define f(i,n)                fr(i,0,n)
#define rf(i,b,a) for(ll i=b-1;i>=a;i--)
#define r(i,n)                rf(i,n,0)
#define eps                   0.000000001
#define sz(a)                int((a).size())
#define all(c)               (c).begin(),(c).end()
#define tr(c,i)              for(typeof(c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x)         ((c).find(x) != (c).end())
#define cpresent(c,x)        (find(all(c),x) != (c).end())
#define pi                   pair<int,int>
#define pll                  pair < ll , ll >
#define endl                 '\n'
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef vector< int > vi;
typedef vector< vi > vvi;
int dx[8]={1,-1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
const ll inf=1000000007;
vector<int> adj[200010],val(200010,0),vis(200010,0),col(200010,0);
int myrandom (int i) { return std::rand()%i;}
//using namespace __gnu_pbds;
//typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> special_map;
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
vector<int> temp(3,0);
void dfs(int a,int co)
{
    vis[a]=1;
    col[a]=co;
    temp[co]++;
    for(auto i:adj[a])
    {
        if(vis[i]==0)
        {
            dfs(i,co^3);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ifstream fin;
    //ofstream fout;
    //fin.open("input.txt");
    //fout.open("output.txt");
    //clock_t launch=clock();
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,1);
    vector<int> v[3];
    for(int i=1;i<=n;i++)
    {
        v[i%3].pb(i);
    }
    if(min(temp[1],temp[2])<=n/3)
    {
        if(temp[1]<=n/3)
        {
            for(int i=1;i<=n;i++)
            {
                if(col[i]==1)
                {
                    val[i]=v[0].back();
                    v[0].pop_back();
                }
                else
                {
                    if(v[1].empty())
                    {
                        if(!v[2].empty())
                        {
                            val[i]=v[2].back();
                            v[2].pop_back();
                        }
                        else
                        {
                            val[i]=v[0].back();
                            v[0].pop_back();
                        }
                    }
                    else
                    {
                        val[i]=v[1].back();
                        v[1].pop_back();
                    }
                }
            }
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(col[i]==2)
                {
                    val[i]=v[0].back();
                    v[0].pop_back();
                }
                else
                {
                    if(v[1].empty())
                    {
                        if(!v[2].empty())
                        {
                            val[i]=v[2].back();
                            v[2].pop_back();
                        }
                        else
                        {
                            val[i]=v[0].back();
                            v[0].pop_back();
                        }
                    }
                    else
                    {
                        val[i]=v[1].back();
                        v[1].pop_back();
                    }
                }
            }
        }
    }
    else
    {
        if(temp[1]<temp[2])
        {
            for(int i=1;i<=n;i++)
            {
                if(col[i]==1)
                {
                    if(v[1].empty())
                    {
                        val[i]=v[0].back();
                        v[0].pop_back();
                    }
                    else
                    {
                        val[i]=v[1].back();
                        v[1].pop_back();
                    }
                }
                else
                {
                    if(v[2].empty())
                    {
                        val[i]=v[0].back();
                        v[0].pop_back();
                    }
                    else
                    {
                        val[i]=v[2].back();
                        v[2].pop_back();
                    }
                }
            }
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(col[i]==2)
                {
                    if(v[1].empty())
                    {
                        val[i]=v[0].back();
                        v[0].pop_back();
                    }
                    else
                    {
                        val[i]=v[1].back();
                        v[1].pop_back();
                    }
                }
                else
                {
                    if(v[2].empty())
                    {
                        val[i]=v[0].back();
                        v[0].pop_back();
                    }
                    else
                    {
                        val[i]=v[2].back();
                        v[2].pop_back();
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<val[i]<<" ";
    }
    cout<<endl;
    //clog<<((long double)(clock()-launch)/CLOCKS_PER_SEC)<<"\n";
}


Measured memory_bytes: 18680