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 _ = 2e5 + 7;
struct Edge{int end , upEd;}Ed[_ << 1];
int head[_] , cntEd , col[2] , N;
void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

void dfs(int x , int p , int c){
	++col[c];
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs(Ed[i].end , x , c ^ 1);
}

vector < int > pot[3]; int arr[_];
void dfs1(int x , int p , int c , int id){
	if(id == 2){
		int i = pot[c + 1].size() ? c + 1 : 0;
		arr[x] = pot[i].back(); pot[i].pop_back();
	}
	else
		if(!(id ^ c)){arr[x] = pot[0].back(); pot[0].pop_back();}
		else{
			int p = pot[1].empty() ? (pot[2].empty() ? 0 : 2) : 1;
			arr[x] = pot[p].back(); pot[p].pop_back();
		}
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs1(Ed[i].end , x , c ^ 1 , id);
}

signed main(){
	cin >> N;
	for(int i = 1 ; i < N ; ++i){int x , y; cin >> x >> y; addEd(x , y); addEd(y , x);}
	for(int i = 1 ; i <= N ; ++i) pot[i % 3].push_back(i);
	dfs(1 , 0 , 0); dfs1(1 , 0 , 0 , col[0] < pot[1].size() ? 0 : (col[1] < pot[2].size() ? 1 : 2));
	for(int i = 1 ; i <= N ; ++i) cout << arr[i] << ' ';
	return 0;
}