#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000
#define bpc(x) __builtin_parityll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

ll getdiam(vector<ll> v[], ll n, ll sta)
{

   ll dis[n];
   memset(dis,-1,sizeof(dis));
   dis[sta] = 1;
   
   queue<ll> q;
   q.push(sta);
   while(q.size()>0)
   {
       ll curr = q.front();
       q.pop();
       
       autoit(v[curr],it)
       {
           if(dis[*it]!=-1)
                continue;
           dis[*it] = dis[curr] + 1;
           q.push(*it);
       }
   }
   
   ll nod = -1;
   ll maxi = 0;
   for(ll i=0;i<n;i++)
   {
       if(dis[i]>maxi)
       {
           maxi = dis[i];
           nod = i;
       }
   }
   
   memset(dis,-1,sizeof(dis));
   dis[nod] = 1;
   
   //queue<ll> q;
   q.push(nod);
   ll par[n];
   par[nod] = -1;
   while(q.size()>0)
   {
       ll curr = q.front();
       q.pop();
       
       autoit(v[curr],it)
       {
           if(dis[*it]!=-1)
                continue;
           dis[*it] = dis[curr] + 1;
           par[*it] = curr;
           q.push(*it);
       }
   }
   
   ll nod1 = -1;
   maxi = 0;
   for(ll i=0;i<n;i++)
   {
       if(dis[i]>maxi)
       {
           maxi = dis[i];
           nod1 = i;
       }
   }
   
   vector<ll> nodes;
   nodes.pb(nod1);
   while(par[nodes.back()]!=-1)
        nodes.pb(par[nodes.back()]);
   return (ll)nodes.size()-1;    
}



int main()
{
   FAST/**/
   
   ll n;
   cin>>n;
   
   vector<ll> v[n];
   vector<ll> val[3];
   for(ll i=1;i<=n;i++)
        val[i%3].pb(i);
   
   rep(n-1)
   {
       ll a,b;
       cin>>a>>b;
       a--,b--;
       v[a].pb(b);
       v[b].pb(a);
   }
   
   if(getdiam(v,n,0) < 3)
   {
       rep(n)
            cout<<i+1<<" ";
       return 0;        
   }
   
   ll col[n];
   col[0] = 0;
   bool vis[n];
   memset(vis,0,sizeof(vis));
   vis[0] = 1;
   queue<ll> q;
   q.push(0);
   while(q.size()>0)
   {
       auto curr = q.front();
       q.pop();
       autoit(v[curr],it)
       {
           if(vis[*it])
                continue;
           vis[*it] = 1;
           col[*it] = 1ll - col[curr];
           q.push(*it);
       }
   }
   
   ll fin[n];
   memset(fin,-1,sizeof(fin));
   ll c1 = 0, c2 = 0;
   ll hold[n+1];
   rep(n){
        if(col[i])
            c1++;
        else c2++;
   }
  // cout<<c1<<" "<<c2<<"\n";        
   if(min(c1,c2)<min((ll)val[1].size(), (ll)val[2].size()))
   {
       if(c2>c1)
       {
           rep(n)
                col[i]^=(1ll);
       }
       
       rep(n)
       {
           if(col[i] == 0)
           {
               hold[val[0].back()] = i+1;
               val[0].pop_back();
               continue;
           }
           
           else
           {
               if(val[1].size()>0)
               {
                   hold[val[1].back()] = i+1;
                   val[1].pop_back();
                   continue;
               }
               
               else if(val[2].size()>0)
               {
                   hold[val[2].back()] = i+1;
                   val[2].pop_back();
                   continue;
               }
               
               else
               {
                   hold[val[0].back()] = i+1;
                   val[0].pop_back();
                   continue;
               }
           }
       }
       
       ll f1[n+1];
       for(ll i=1;i<=n;i++)
            f1[hold[i]] = i;
       
       rep(n)
            cout<<f1[i+1]<<" ";
        return 0;
   }
   
   if(c2>c1)
   {
       rep(n)
            col[i]^=(1ll);
   }
   
   if(val[1].size()>val[2].size())
   {
       rep(n){
        if(col[i] == 0)
        {
            if(val[2].size()>0)
            {
                hold[val[2].back()] = i+1;
                val[2].pop_back();
            }
            
            else
            {
                hold[val[0].back()] = i+1;
                val[0].pop_back();
            }
        }
        
        else
        {
            if(val[1].size()>0)
            {
                hold[val[1].back()] = i+1;
                val[1].pop_back();
            }
            
            else
            {
                hold[val[0].back()] = i+1;
                val[0].pop_back();
            }
        }
       }
   }
   
   else
   {
       rep(n){
        if(col[i] == 1)
        {
            if(val[2].size()>0)
            {
                hold[val[2].back()] = i+1;
                val[2].pop_back();
            }
            
            else
            {
                hold[val[0].back()] = i+1;
                val[0].pop_back();
            }
        }
        
        else
        {
            if(val[1].size()>0)
            {
                hold[val[1].back()] = i+1;
                val[1].pop_back();
            }
            
            else
            {
                hold[val[0].back()] = i+1;
                val[0].pop_back();
            }
        }
       }
   }
   ll f1[n+1];
       for(ll i=1;i<=n;i++)
            f1[hold[i]] = i;
       
       rep(n)
            cout<<f1[i+1]<<" ";
   
   
   
   return 0;        
}  
   

Measured memory_bytes: 23260