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;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

VVI edge(214514, VI(0));
VI ans(214514);
int n;
int c[2]={0,0};
int pn[3]={3,1,2};
bool f;
void check(int v, int p, int d) {
	c[d]++;
	for (int i = 0; i < edge[v].size(); i++) {
		if (edge[v][i] != p) {
			check(edge[v][i], v, !d);
		}
	}
}
void dfs(int v, int p, int d) {
	int num;
	if(d)
		num=1;
	else
		num=2;
	if(pn[num]<=n){
		ans[v]=pn[num];
		pn[num]+=3;
	}
	else{
		ans[v]=pn[0];
		pn[0]+=3;
	}
	for (int i = 0; i < edge[v].size(); i++) {
		if (edge[v][i] != p) {
			dfs(edge[v][i], v, !d);
		}
	}
}

void dfs2(int v, int p, int d, int f){
	if(d==f){
		ans[v]=pn[0];
		pn[0]+=3;
	}
	else{
		REP(i,3){
			if(pn[(i+1)%3]<=n){
				ans[v]=pn[(i+1)%3];
				pn[(i+1)%3]+=3;
				break;
			}
		}
	}
	for (int i = 0; i < edge[v].size(); i++) {
		if (edge[v][i] != p) {
			dfs2(edge[v][i], v, !d, f);
		}
	}
}

int main() {
	cin >> n;
	int a, b;
	REP(i,n-1){
		cin >> a >> b;
		a--; b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	check(0,-1,0);
	if(c[0]>n/3&&c[1]>n/3){
		dfs(0,-1,0);
	}
	else{
		if(c[0]>n/3){
			dfs2(0,-1,0,1);
		}
		else{
			dfs2(0,-1,0,0);
		}
	}
	REP(i,n)cout << ans[i] << (i==n-1?'\n':' ');
	return 0;
}