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 rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using graph=vector<vector<int>>;

int n;
graph T;

vector<int> color;

void dfs(int u,int p,int dep){
	color[u]=dep%2;
	for(int v:T[u]) if(v!=p) dfs(v,u,dep+1);
}

int main(){
	scanf("%d",&n);
	T.resize(n);
	rep(i,n-1){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		T[u].emplace_back(v);
		T[v].emplace_back(u);
	}

	color.resize(n);
	dfs(0,-1,0);

	int nb=count(color.begin(),color.end(),0);
	int nw=count(color.begin(),color.end(),1);

	if(nb>nw){
		swap(nb,nw);
		rep(u,n) color[u]=1-color[u];
	}

	vector<int> ans(n);
	if(nb<=n/3){
		int bcnt=3,wcnt=1;
		rep(u,n){
			if(color[u]==0) ans[u]=bcnt, bcnt+=3;
			else            ans[u]=wcnt, wcnt+=(wcnt%3==1?1:2);
		}
		rep(u,n) if(ans[u]>n) ans[u]=bcnt, bcnt+=3;
	}
	else{
		int bcnt=1,wcnt=2;
		rep(u,n){
			if(color[u]==0) ans[u]=bcnt, bcnt+=3;
			else            ans[u]=wcnt, wcnt+=3;
		}
		int cnt=3;
		rep(u,n) if(ans[u]>n) ans[u]=cnt, cnt+=3;
	}
	rep(u,n) printf("%d%c",ans[u],u<n-1?' ':'\n');

	return 0;
}