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>
using namespace std ;
const int N = 2e5 + 10 ;
int a[N] ;
vector<int> v[N] ;
int n , vis[N] , dep[N] , b[N] ;
int d[4] = {0 , 1 , 2 , 3} ;
void dfs(int u , int fa , int d)
{
	dep[u] = d ;
	vis[u] = 1 ;
	for(auto x : v[u])
	 {
		 if(x == fa || vis[x]) continue ;
		 dfs(x , u , d + 1) ;
	 }
}
int main()
{
	scanf("%d" , &n) ;
	for(int i = 1 , x , y ; i < n ;i ++)
	 scanf("%d%d" , &x , &y) , v[x].push_back(y) , v[y].push_back(x) ;
  dep[1] = 1;
	dfs(1 , -1 , 1) ;
  int c = 0 ;
	for(int i = 1; i <= n ;i ++)
	 c += dep[i] % 2 ;
  b[3] = n / 3 , b[1] = n / 3 + (n % 3 >= 1) , b[2] = n / 3 + (n % 3 >= 2) ;
	if(c <= n / 3 || (n - c) <= n / 3)
	 {
		 int y = 1 ;
		 if(c > n / 3) y = 0 ;
		 for(int i = 1 ; i <= n ;i ++)
		  if(dep[i] % 2 == y) a[i] = 3 ;
			else
			{
				if(b[1]) a[i] = 1 , b[1] -- ;
				else if(b[2]) a[i] = 2 , b[2] -- ;
				else if(b[3]) a[i] = 3 , b[3] -- ;
			}
	 }
	 else
	 {
		 for(int i = 1 ;i <= n ;i ++)
		  {
				if(dep[i] % 2)
				 {
					 if(b[1]) a[i] = 1 , b[1] -- ;
					 else if(b[3] ) a[i] = 3 , b[3] -- ;
				 }
				else
				 {
					 if(b[2]) a[i] = 2 , b[2] -- ;
					 else if(b[3]) a[i] = 3 , b[3] -- ;
				 }
			}
	 }
	 b[1] = 0 , b[2] = 0 , b[3] = 0 ;

	 for(int i = 1; i <= n ;i ++)
			 a[i] = d[a[i]] + ((b[a[i]] ++ ) * 3 ) , cout << a[i] << " " ;
	puts("") ;
	return 0 ;
}