// Original C++ solution (slower):
//Coded by tzc_wk

/*

数据不清空，爆零两行泪。

多测不读完，爆零两行泪。

边界不特判，爆零两行泪。

贪心不证明，爆零两行泪。

D P 顺序错，爆零两行泪。

大小少等号，爆零两行泪。

变量不统一，爆零两行泪。

越界不判断，爆零两行泪。

调试不注释，爆零两行泪。

溢出不 l l，爆零两行泪。

*/

#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

#define fz(i,a,b)	for(int i=a;i<=b;i++)

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)		a.begin(),a.end()

#define giveup(...) return printf(__VA_ARGS__),0;

#define fill0(a)	memset(a,0,sizeof(a))

#define fill1(a)	memset(a,-1,sizeof(a))

#define fillbig(a)	memset(a,0x3f,sizeof(a))

#define fillsmall(a) memset(a,0xcf,sizeof(a))

#define mask(a)		(1ll<<(a))

#define maskx(a,x)	((a)<<(x))

#define _bit(a,x)	(((a)>>(x))&1)

#define _sz(a)		((int)(a).size())

#define filei(a)	freopen(a,"r",stdin);

#define fileo(a)	freopen(a,"w",stdout);

#define fileio(a) 	freopen(a".in","r",stdin);freopen(a".out","w",stdout)

#define eprintf(...) fprintf(stderr,__VA_ARGS__)

#define put(x)		putchar(x)

#define eoln        put('\n')

#define space		put(' ')

#define y1			y_chenxiaoyan_1

#define y0			y_chenxiaoyan_0

typedef pair<int,int> pii;

inline int read(){

	int x=0,neg=1;char c=getchar();

	while(!isdigit(c)){

		if(c=='-')	neg=-1;

		c=getchar();

	}

	while(isdigit(c))	x=x*10+c-'0',c=getchar();

	return x*neg;

}

inline void print(int x){

	if(x<0){

		putchar('-');

		print(abs(x));

		return;

	}

	if(x<=9)	putchar(x+'0');

	else{

		print(x/10);

		putchar(x%10+'0');

	}

}

inline int qpow(int x,int e,int _MOD){

	int ans=1;

	while(e){

		if(e&1)	ans=ans*x%_MOD;

		x=x*x%_MOD;

		e>>=1;

	}

	return ans;

}

int n=read();

vector<int> g[200005];

int col[200005];

int cnt[2],a[200005];

inline void dfs(int x,int fa){

	col[x]=col[fa]^1;

	cnt[col[x]]++;

	foreach(it,g[x]){

		int y=*it;

		if(y==fa)	continue;

		dfs(y,x);

	}

}

signed main(){

	fz(i,1,n-1){

		int x=read(),y=read();

		g[x].push_back(y);

		g[y].push_back(x);

	}

	dfs(1,0);

	set<int> st;

	fz(i,1,n)	st.insert(i);

	if(cnt[0]<=n/3){

		int cnt1=0;

		fz(i,1,n)	if(col[i]==0)	cnt1++,a[i]=cnt1*3,st.erase(st.find(a[i]));

		fz(i,1,n){

			if(!a[i])	a[i]=*st.begin(),st.erase(st.begin());

		}

	}

	else if(cnt[1]<=n/3){

		int cnt1=0;

		fz(i,1,n)	if(col[i]==1)	cnt1++,a[i]=cnt1*3,st.erase(st.find(a[i]));

		fz(i,1,n){

			if(!a[i])	a[i]=*st.begin(),st.erase(st.begin());

		}

	}

	else{

		int cnt1=0,cnt2=0;

		fz(i,1,n){

//			cout<<col[i]<<endl;

			if(col[i]==0&&cnt1*3+1<=n)	a[i]=cnt1*3+1,cnt1++,st.erase(st.find(a[i]));

			if(col[i]==1&&cnt2*3+2<=n)	a[i]=cnt2*3+2,cnt2++,st.erase(st.find(a[i]));

			}

		fz(i,1,n){

			if(!a[i])	a[i]=*st.begin(),st.erase(st.begin());

		}

	}

	fz(i,1,n)	cout<<a[i]<<" ";

	return 0;

}

// Optimized solution to the same problem (faster):
/*

Date&Time: 12:19pm 3/10/2020

*/



#include <bits/stdc++.h>



using namespace std;



#define int long long



const int N = 2e5 + 10;



int ver[N * 2], nex[N * 2], head[N], cnt[2], ans[N], color[N];

int n, tot;

vector<int> a[3];



inline void add(int x, int y) {

	ver[++tot] = y;

	nex[tot] = head[x];

	head[x] = tot;

}



void dfs(bool c, int x, int fa) {

	color[x] = c;

	cnt[c]++;

	for (int i = head[x]; i; i = nex[i]) {

		int y = ver[i];

		if (y == fa) continue;

		dfs(!c, y, x);

	}

}



signed main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {

		a[i % 3].push_back(i);

	}

	for (int i = 1, u, v; i < n; i++) {

		cin >> u >> v;

		add(u, v), add(v, u);

	}

	dfs(1, 1, 0);

	int fl = 0;

	int r = cnt[0], b = cnt[1];

	if (r > b) swap(r, b), fl = !fl;

	int x = n / 3;

	int zero = 0, one = 0, two = 0;

	if (r <= x) {

		for (int i = 1; i <= n; i++) {

			if (color[i] == fl) {

				ans[i] = a[0][zero++];

			}

			else {

				ans[i] = one < a[1].size() ? a[1][one++] : two < a[2].size() ? a[2][two++] : a[0][zero++];

			}

		}

	}

	else{

		for (int i = 1; i <= n; i++) {

			if (color[i] == fl) {

				ans[i] = one < a[1].size() ? a[1][one++] : zero < a[0].size() ? a[0][zero++] : a[1][one++];

			}

			else {

				ans[i] = two < a[2].size() ? a[2][two++] : zero < a[0].size() ? a[0][zero++] : a[1][one++];

			}

		}

	}

	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

	cout << '\n';

}

// Fastest known solution for this problem: