Problem: We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

* For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.



Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

* 2\leq N\leq 2\times 10^5
* 1\leq a_i, b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}


Output

If no permutation satisfies the condition, print `-1`.

Otherwise, print a permutation satisfying the condition, with space in between. If there are multiple solutions, you can print any of them.

Example

Input

5
1 2
1 3
3 4
3 5


Output

1 2 5 4 3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ll long long
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
using namespace std;
const int inf=1e9+10;
const int mod=1e9+7;
const int maxn=2e5+10;
int d[maxn],ans[maxn],n;
vector<int>g[maxn];
queue<int>c[3],a[2];
void dfs(int u,int fa){
	d[u]=d[fa]+1;
	for(int x:g[u]){
		if(x==fa) continue;
		dfs(x,u);
	}
}
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].pb(y);g[y].pb(x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) c[i%3].push(i);
	for(int i=1;i<=n;i++) a[d[i]%2].push(i);
	if(a[0].size()>a[1].size()) swap(a[0],a[1]);
	if(a[0].size()<=n/3){
		while(!a[0].empty()){
			int x=a[0].front();a[0].pop();
			int y=c[0].front();c[0].pop();
			ans[x]=y;
		}
		while(!a[1].empty()){
			int x=a[1].front();a[1].pop();
			for(int i=0;i<3;i++) if(!c[i].empty()){
				ans[x]=c[i].front();c[i].pop();
				break;
			}
		}
	}else{
		while(!c[1].empty()){
			int x=a[0].front();a[0].pop();
			int y=c[1].front();c[1].pop();
			ans[x]=y;
		}
		while(!c[2].empty()){
			int x=a[1].front();a[1].pop();
			int y=c[2].front();c[2].pop();
			ans[x]=y;
		}
		for(int i=0;i<2;i++){
			while(!a[i].empty()){
				int x=a[i].front();a[i].pop();
				int y=c[0].front();c[0].pop();
				ans[x]=y;
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d%c",ans[i],i==n?'\n':' ');
	}
	return 0;
}
/*

1,2,3,4,5
2,1,2,1,0,1,0
*/