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 MAXN 200002

int n;
bool vis[MAXN] = {false}, use[MAXN] = {false};
vector <int> e[MAXN], r[3], g[2];
int col[MAXN] = {0}, p[3] = {0};

void color (int x, int sig) {
    g[sig & 1].push_back (x);
    vis[x] = true;
    for (int i = 0; i < e[x].size (); i ++)
        if (!vis[e[x][i]])
            color (e[x][i], sig ^ 1);
}

int main () {
    cin >> n;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        e[u].push_back (v); e[v].push_back (u);
        r[i % 3].push_back (i);
    }
    r[n % 3].push_back (n);
    
    color (1, 1);
    
    if (g[0].size () > g[1].size ()) {
        vector <int> tmp = g[0];
        g[0] = g[1]; g[1] = tmp;
    }

    if (g[0].size () <= n / 3) {
        for (int i = 0; i < g[0].size (); i ++) 
            col[g[0][i]] = r[0][p[0]], use[r[0][p[0] ++]] = true; 
        int pf = 1;
        for (int i = 0; i < g[1].size (); i ++) {
            if (use[pf]) pf ++;
            col[g[1][i]] = pf ++;
        } 
    }
    else {
        for (int i = 0; i < g[0].size (); i ++)
            if (p[1] < r[1].size ())
                col[g[0][i]] = r[1][p[1] ++];
            else col[g[0][i]] = r[0][p[0] ++];
        
        for (int i = 0; i < g[1].size (); i ++)
            if (p[2] < r[2].size ())
                col[g[1][i]] = r[2][p[2] ++];
            else col[g[1][i]] = r[0][p[0] ++];        
    }

    for (int i = 1; i <= n; i ++)
        cout << col[i] << " ";

    return 0;
}