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 endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < (n); i++)
#define forr(i,a,b) for (int i = (a); i <= (b); i++)
#define all(v) v.begin(), v.end()
#define pb push_back
 
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;

const int MX = 200005;
int n, res[MX], cn[3], f = 0, lvl[2];
vi adj[MX];

void dfs (int u, int l, int p = -1) {
	lvl[l]++;
	for (int v : adj[u])
		if (v != p)
			dfs(v, 1 - l, u);
} 

void go (int u, int l, int x, int y, int p = -1) {
	if (cn[1] && l == x) {
		res[u] = 1;
		cn[1]--;
	} else if (cn[2] && l == y) {
		res[u] = 2;
		cn[2]--;
	}

	for (int v : adj[u])
		if (v != p)
			go(v, 1 - l, x, y, u);
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}

	cn[0] = n / 3;
	cn[1] = (n + 2) / 3;
	cn[2] = (n + 1) / 3;
	
	dfs(1, 0);

	if (cn[1] + cn[2] <= lvl[0]) go(1, 0, 0, 0);
	else if (cn[1] + cn[2] <= lvl[1]) go(1, 0, 1, 1);
	else go(1, 0, 0, 1);

	cn[0] = 3;
	cn[1] = 1;
	cn[2] = 2;

	for (int i = 1; i <= n; i++) {
		cout << cn[res[i]] << " ";
		cn[res[i]] += 3;
	}
	cout << endl;

	return 0;
}