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_ = 200100;
vector<int> V[N_], G[N_], E[N_];
int N, Co[N_], Res[N_];
void Haku(int s, int e) {
	Co[s] = !Co[e];
	G[Co[s]].push_back(s);
	for (auto &u : V[s]) if (u != e) Haku(u, s);
}
int main() {
	int i, p = 0;
	scanf("%d", &N);
	for (i = 1; i <= N; ++i) E[i % 3].push_back(i);
	for (i = 1; i + 1 <= N; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		V[a].push_back(b);
		V[b].push_back(a);
	}
	Haku(1, 1);
	if (G[1].size() < G[0].size()) p = !p;
	if (G[p].size() <= E[0].size()) {
		for (i = 1; i <= N; ++i) if (Co[i] == p) {
			Res[i] = E[0].back();
			E[0].pop_back();
		}
		for (i = 1; i <= N && E[1].size(); ++i) if (!Res[i]) {
			Res[i] = E[1].back();
			E[1].pop_back();
		}
		for (i = 1; i <= N && E[2].size(); ++i) if (!Res[i]) {
			Res[i] = E[2].back();
			E[2].pop_back();
		}
	} else {
		for (i = 1; i <= N && E[1].size(); ++i) if (Co[i]) {
			Res[i] = E[1].back();
			E[1].pop_back();
		}
		for (i = 1; i <= N && E[2].size(); ++i) if (!Co[i]) {
			Res[i] = E[2].back();
			E[2].pop_back();
		}
	}
	for (i = 1; i <= N; ++i) if (!Res[i]) {
		Res[i] = E[0].back();
		E[0].pop_back();
	}
	for (i = 1; i <= N; ++i) printf("%d ", Res[i]);
	puts("");
}