#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pb push_back
#define ii pair<int,int>
#define ppb pop_back
#define orta ((bas+son)>>1)
#define st first
#define nd second
#define ll long long
#define N 200005
#define inf 1000000000
#define MOD 1000000007
#define LOG 29
#define EPS 0.000000001
#define M 305
using namespace std;

int n;
int cur[3],ans[N],now[3],mark[N];
vector<int> v[N],w[3];

int nxt(int m) {

	mark[now[m]]=1;
	now[m]+=3;
	return now[m]-3;

}

void dfs(int node,int dad,int c) {

	w[c].pb(node);
	for(int i:v[node]) {
		if(i!=dad) {
			dfs(i,node,!c);
		}
	}

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);	

	cin>>n;
	for(int i=1,x,y;i<n;i++) {
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	now[0]=3;
	now[1]=1;
	now[2]=2;
	for(int i=0;i<3;i++) {
		cur[i]=n/3+(n%3>=i && i);
	}
	dfs(1,0,0);
	if(sz(w[0])>sz(w[1]))
		swap(w[0],w[1]);
	int c=0;
	if(sz(w[0])>cur[0]) {
		c=1;		
	}	
	while(sz(w[0])) {
		int node=w[0].back();
		w[0].ppb();
		if(!cur[c]) c--;
		ans[node]=nxt(c);
		cur[c]--;
	}
	int ptr=1;
	for(auto x:w[1]) {
		while(mark[ptr]) ptr++;
		ans[x]=ptr;
		ptr++;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";

}