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:
#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef struct{int x;int y;}H;
int a,b,i,j,k,l,m,n,s,sz,t,pv[200040],vi[200040],d[200040],u[200040],z[200040];
H e[400005];
int C(H a,H b){return a.x<b.x;}
void dfs(int v,int k)
{
	vi[v]=1;
	d[v]=k;
	if(k)a++;
	else b++;
	for(int i=pv[v];i<pv[v+1];i++)
	{
		if(!vi[e[i].y])dfs(e[i].y,!k);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(;i<n-1;i++)
	{
		cin>>e[i].x>>e[i].y;
		e[i+n-1].x=e[i].y;
		e[i+n-1].y=e[i].x;
	}
	sz=2*n-2;
	sort(e,e+sz,C);
	for(i=0;++i<sz;)
	{
		if(e[i].x>e[i-1].x)
		{
			for(j=e[i-1].x;j++<e[i].x;)
			{
				pv[j]=i;
			}
		}
	}
	for(j=e[sz-1].x;j++<n+1;)pv[j]=sz;
	dfs(1,1);
	{
		if(a<b)
		{
			for(i=0;i++<n;)d[i]=!d[i];
			swap(a,b);
		}
		if(b<=n/3)
		{
			for(i=0,k=3;i++<n;)
			{
				if(!d[i])
				{
					z[i]=k;
					u[k]=1;
					k+=3;
				}
			}
			for(i=0,l=1;i++<n;)
			{
				if(d[i])
				{
					z[i]=l++;
					if(u[l])l++;
				}
			}
		}
		else
		{
			for(i=0,k=1;i++<n;)
			{
				if(d[i])
				{
					z[i]=k;
					k+=3;
					if(k>n)k=3;
				}
			}
			for(i=0,l=2;i++<n;)
			{
				if(!d[i])
				{
					z[i]=l;
					l+=3;
					if(l>n)l=k;
				}
			}
		}
		for(i=0;i++<n;)cout<<z[i]<<' ';
	}
}