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 sz(x) ((int)x.size())
#define pb push_back
#define ii pair<int,int>
#define ppb pop_back
#define orta ((bas+son)>>1)
#define st first
#define nd second
#define ll long long
#define N 200005
#define inf 1000000000
#define MOD 1000000007
#define LOG 29
#define EPS 0.000000001
#define M 305
using namespace std;

int n;
int cur[3],ans[N],now[3],mark[N];
vector<int> v[N],w[3];

int nxt(int m) {

	mark[now[m]]=1;
	now[m]+=3;
	return now[m]-3;

}

void dfs(int node,int dad,int c) {

	w[c].pb(node);
	for(int i:v[node]) {
		if(i!=dad) {
			dfs(i,node,!c);
		}
	}

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);	

	cin>>n;
	for(int i=1,x,y;i<n;i++) {
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	now[0]=3;
	now[1]=1;
	now[2]=2;
	for(int i=0;i<3;i++) {
		cur[i]=n/3+(n%3>=i && i);
	}
	dfs(1,0,0);
	if(sz(w[0])>sz(w[1]))
		swap(w[0],w[1]);
	int c=0;
	if(sz(w[0])>cur[0]) {
		c=1;		
	}	
	while(sz(w[0])) {
		int node=w[0].back();
		w[0].ppb();
		if(!cur[c]) c--;
		ans[node]=nxt(c);
		cur[c]--;
	}
	int ptr=1;
	for(auto x:w[1]) {
		while(mark[ptr]) ptr++;
		ans[x]=ptr;
		ptr++;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";

}