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 LL long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
using namespace std;

const int N = 2e5 + 5;

int ans[N];
vector < int > G[N];
vector < int > Q[2];
vector < int > P[3];

void dfs(int u, int fa, int op) {
    Q[op].pb(u);
    for(auto v : G[u]) {
        if(v == fa) continue;
        dfs(v, u, op ^ 1);
    }
}

void add(int op1, int op2) {
    while(!Q[op1].empty() && !P[op2].empty()) {
        ans[Q[op1].back()] = P[op2].back();
        Q[op1].pop_back();
        P[op2].pop_back();
    }
}

void solve() {

    int n;
    scanf("%d", &n);
    rep(i, 1, n) P[i % 3].pb(i);
    rep(i, 1, n - 1) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1, 0, 0);

    if(Q[0].size() > Q[1].size()) add(0, 1);
    else add(1, 1);

    if(Q[0].size() > Q[1].size()) add(0, 2);
    else add(1, 2);

    add(0, 0);
    add(1, 0);

    rep(i, 1, n) printf("%d ", ans[i]); puts("");
}


int main() {
//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}