#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
 
template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
	ll ans=1;
	while(n){
		if(n&1) ans=(ans*a)%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans%mod;
}
//==============================================================
const int maxn=2e5+10;
struct Edge{
    int to,next;
}e[maxn<<1];
int par[maxn];
int depth[maxn];
int ans[maxn];
int n;
int head[maxn],cnt;
void add(int x,int y){
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
int vis[maxn];
int ji,ou;
void dfs(int u,int fa,int de){
    depth[u]=de;
    vis[u]=1;
    if(de%2) ji++;
    else ou++;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(vis[v]) continue;
        dfs(v,u,de+1);
    }
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	clock_t c1 = clock();
	//===========================================================
	read(n);
    memset(head,-1,sizeof(head));
    rep(i,2,n){
        int a,b;
        read(a),read(b);
        add(a,b),add(b,a);
    }
    int pos[3]={1,0,0};
    dfs(1,-1,0);
    if(ji*3>=n&&ou*3>=n){
        int pos0=1,pos1=0,pos2=0;
        rep(i,1,n){
            if(depth[i]%2&&(pos1*3+1)<=n){
                ans[i]=pos1*3+1;
                pos1++;
            }
            else if(depth[i]%2==0&&(pos2*3+2)<=n){
                ans[i]=pos2*3+2;
                pos2++;
            }
        }
        rep(i,1,n){
            if(ans[i]==0){
                ans[i]=pos0*3;
                pos0++;
            }
        }
    }
    else if(ji*3<=n){
        int pos0=1;
        int vis[maxn]={0};
        rep(i,1,n){
            if(depth[i]%2){
                ans[i]=pos0*3;
                pos0++;
                vis[ans[i]]=1;
            }
        }
        int p=1;
        rep(i,1,n){
            if(ans[i]==0){
                while(vis[p]) p++;
                ans[i]=p;
                p++;
            }
        }
    }
    else if(ou*3<=n){
        int pos0=1;
        int vis[maxn]={0};
        rep(i,1,n){
            if(!(depth[i]%2)){
                ans[i]=pos0*3;
                pos0++;
                vis[ans[i]]=1;
            }
        }
        int p=1;
        rep(i,1,n){
            if(!ans[i]){
                while(vis[p])p++;
                ans[i]=p;
                p++;
            }
        }
    }
    rep(i,1,n){
        if(i-1) putchar(' ');
        write(ans[i]);
    }
	//===========================================================
	std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
	return 0;
}

Measured memory_bytes: 12800