/*#include <set>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
void read(int &a){
	a=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a=(a<<1)+(a<<3)+(c^48);
		c=getchar();
	}
}
const int Maxn=200000;
int n;
int f[4][Maxn+5],fa[4][Maxn+5],g[Maxn+5];
int head[Maxn+5],arrive[Maxn<<1|5],nxt[Maxn<<1|5],tot;
int a[Maxn+5];
set<int> num[4][Maxn+5];
void add_edge(int from,int to){
	arrive[++tot]=to;
	nxt[tot]=head[from];
	head[from]=tot;
}
void init_dfs_1(int u,bool flag){
	fa[2][u]=fa[1][fa[1][u]];
	fa[3][u]=fa[2][fa[1][u]];
	if(a[u]==0||a[u]%3!=0){
		f[0][u]=1;
		if(flag){
			num[0][u].insert(u);
		}
	}
	for(int i=head[u];i;i=nxt[i]){
		int v=arrive[i];
		if(fa[1][u]==v){
			continue;
		}
		fa[1][v]=u;
		init_dfs_1(v,flag);
		if(flag&&(a[u]==0||a[u]%3!=0)){
			for(int k=0;k<3;k++){
				for(auto j:num[k][v]){
					num[k+1][u].insert(j);
				}
			}
		}
		f[1][u]+=f[0][v];
		f[2][u]+=f[1][v];
		f[3][u]+=f[2][v];
	}
}
void init_dfs_2(int u,bool flag){
	g[u]=f[3][u];
	if(fa[1][u]){
		g[u]+=f[2][fa[1][u]]-f[1][u];
	}
	if(fa[2][u]){
		g[u]+=f[1][fa[2][u]]-1;
	}
	if(fa[3][u]){
		g[u]+=f[0][fa[3][u]];
	}
	for(int i=head[u];i;i=nxt[i]){
		int v=arrive[i];
		if(fa[1][u]==v){
			continue;
		}
		init_dfs_2(v,flag);
	}
	if(flag&&(a[u]==0||a[u]%3!=0)){
		for(int k=0;k<3;k++){
			if(fa[3-k][u]){
				for(auto j:num[k][fa[3-k][u]]){
					if(3-k==1){
						if(num[1][u].count(j)==0){
							num[1][u].insert(j);
						}
					}
					else if(3-k==1){
						if(j==fa[1][u]){
							num[1][u].insert(j);
						}
					}
					else{
						num[1][u].insert(j);
					}
				}
			}
		}
	}
}
int id[Maxn+5];
int id_tot;
bool used[Maxn+5];
bool cmp(int p,int q){
	return g[p]>g[q];
}
queue<int> q;
int main(){
	read(n);
	int u,v;
	for(int i=1;i<n;i++){
		read(u),read(v);
		add_edge(u,v);
		add_edge(v,u);
	}
	init_dfs_1(1,0);
	init_dfs_2(1,0);
	for(int i=1;i<=n;i++){
		id[i]=i;
	}
	sort(id+1,id+1+n,cmp);
	for(int i=1;i<=n/3;i++){
		a[id[i]]=i*3;
		used[i*3]=1;
	}
	init_dfs_1(1,1);
	init_dfs_2(1,1);
	int last=0;
	int mod_3_1=-2,mod_3_2=-1;
	while(id_tot<n){
		for(int i=last+1;i<=n;i++){
			if(a[i]==0){
				q.push(i);
				last=i;
				id_tot++;
				while(used[id_tot]){
					id_tot++;
				}
				used[id_tot]=1;
				a[i]=id_tot;
				break;
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(auto v:num[3][u]){
				if(a[v]==0){
					if(a[u]%3==1){
						mod_3_2+=3;
						while(used[mod_3_2]){
							mod_3_2+=3;
						}
						a[v]=mod_3_2;
						used[mod_3_2]=1;
					}
					else{
						mod_3_1+=3;
						while(used[mod_3_1]){
							mod_3_1+=3;
						}
						a[v]=mod_3_1;
						used[mod_3_1]=1;
					}
					q.push(v);
				}
				else{
					if(a[v]%3!=0&&(a[v]+a[u])%3!=0){
						puts("-1");
						return 0;
					}
				}
			}
		}
		while(used[id_tot+1]){
			id_tot++;
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	puts("");
	return 0;
}
*/
#include <vector>
#include <cstdio>
using namespace std;
const int Maxn=200000;
int ans[Maxn+5];
vector<int> G[Maxn+5],col[2],mod[3];
void dfs(int x,int c,int fa){
	col[c].push_back(x);
	for (auto y:G[x]){
		if(y!=fa){
			dfs(y,c^1,x);
		}
	}
}
void sol(int i,int j){
	while(!col[i].empty()&&!mod[j].empty()){
		ans[col[i].back()]=mod[j].back();
		col[i].pop_back();
		mod[j].pop_back();
	}
}
int main(){
	int n;
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		mod[i%3].push_back(i);
	}
	dfs(1,0,0);
	sol(col[0].size()<col[1].size(),1);
	sol(col[0].size()<col[1].size(),2);
	sol(0,0);
	sol(1,0);
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}


Measured memory_bytes: 22296