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;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define N 212345
int n;
vi g[N];
set<int> a[2];
int ans[N];

void dfs(int i, int p, int d){
	a[d%2].emplace(i);
	for(int &j : g[i]){
		if(j == p) continue;
		dfs(j, i, d+1);
	}
}
int f(int x){
	REP(i, 2) if((int)a[i].size() >= x) return i;
	assert(false);
}
void h(int p, int i){
	auto it = a[p].begin();
	ans[*it] = i;
	a[p].erase(it);
}
void gg(int k){
	int cnt, p;
	cnt = 0;
	for(int i = k; i <= n; i += 3) cnt++;
	p = f(cnt);
	for(int i = k; i <= n; i += 3) {
		h(p, i);
	}
}

int main(){
	scanf("%d", &n);
	REP(i, n-1){
		int a, b; scanf("%d%d", &a, &b);
		g[a].EB(b);
		g[b].EB(a);
	}
	dfs(1, 0, 0);

	gg(1);
	gg(2);

	for(int i = 3; i <= n; i += 3){
		h(f(1), i);
	}

	for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
}