/*
khoi orz, go check out his algo
-normie-
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define FILE_IN "robot.inp"
#define FILE_OUT "robot.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define ord(a,b,c) ((a>=b)and(b>=c))
#define MOD (ll(1000000007))
#define MAX 300001
#define mag 1048576
#define fi first
#define se second
#define pow2(x) (ll(1)<<x)
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define For(i,__,___) for(int i=__;i<=___;i++)
#define Rep(i,__,___) for(int i=__;i>=___;i--)
#define ordered_set tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
#define bi BigInt
#define ll long long
#define pi 3.1415926535897
//------START-----------//
struct node
{
	int match;
	int gt[2];
	node()
	{
		match=0;
		gt[0]=-1; gt[1]=-1;
	}
};
//------END-----------//
ll n,m,k,t,t1,i,j,a,b, res=-1,resi,resj,fin[200001],used[200001];
vector<ll> gt[200001],bi_1,bi_2,ass_1,ass_2,ass_3,num_1,num_2,num_3;
void dfs(int x, int c)
{
 // cout<<"dfs("<<x<<","<<c<<")\n";
	used[x]=c;
	if (c==1)
	{
		bi_1.push_back(x);
	}
	else bi_2.push_back(x);
	for (auto g: gt[x])
	{
		if (!used[g]) dfs(g,3-c);
	}
}
int main()
{
//	ofile;
	fio;
	cin>>n;
	for (i=1;i<n;i++)
	{
		cin>>a>>b;
		gt[a].push_back(b);
		gt[b].push_back(a);
	}
	for (i=1;i<=n;i++)
	{
		if (i%3==0) num_3.push_back(i);
		if (i%3==1) num_1.push_back(i);
		if (i%3==2) num_2.push_back(i);
	}
	
	dfs(1,1);
	if (bi_1.size()<=num_3.size())
	{
		for (i=0;i<bi_1.size();i++)
		{
			ass_3.push_back(bi_1[bi_1.size()-1]);
			bi_1.pop_back();
		}
		for (auto g:bi_1) bi_2.push_back(g);
		for (i=ass_3.size();i<num_3.size();i++)
		{
			
			ass_3.push_back(bi_2[bi_2.size()-1]);
			bi_2.pop_back();
		}
		for (i=0;i<num_1.size();i++)
		{
			
			ass_1.push_back(bi_2[bi_2.size()-1]);
			bi_2.pop_back();
		}
		for (i=0;i<num_2.size();i++)
		{
			
			ass_2.push_back(bi_2[bi_2.size()-1]);
			bi_2.pop_back();
		}
	}
	else
	
	if (bi_2.size()<=num_3.size())
	{
		for (i=0;i<bi_2.size();i++)
		{
			ass_3.push_back(bi_2[bi_2.size()-1]);
			bi_2.pop_back();
		}
		for (auto g:bi_2) bi_1.push_back(g);
		for (i=ass_3.size();i<num_3.size();i++)
		{
			
			ass_3.push_back(bi_1[bi_1.size()-1]);
			bi_1.pop_back();
		}
		for (i=0;i<num_1.size();i++)
		{
			
			ass_1.push_back(bi_1[bi_1.size()-1]);
			bi_1.pop_back();
		}
		for (i=0;i<num_2.size();i++)
		{
			
			ass_2.push_back(bi_1[bi_1.size()-1]);
			bi_1.pop_back();
		}
	}
	else
	{
	
	for (i=0;i<num_1.size();i++)
	{
		ass_1.push_back(bi_1[bi_1.size()-1]);
		bi_1.pop_back();
	}
	for (i=0;i<num_2.size();i++)
	{
		ass_2.push_back(bi_2[bi_2.size()-1]);
		bi_2.pop_back();
	}
	
	for (auto g: bi_1) ass_3.push_back(g);
	for (auto g: bi_2) ass_3.push_back(g);
	}
	for (i=0;i<num_1.size();i++) fin[ass_1[i]]=num_1[i];
	for (i=0;i<num_2.size();i++) fin[ass_2[i]]=num_2[i];
	for (i=0;i<num_3.size();i++) fin[ass_3[i]]=num_3[i];
	
	for (i=1;i<=n;i++) cout<<fin[i]<<' ';
}

Measured memory_bytes: 24552