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 int long long
using namespace std;
constexpr int mod=1e9+7;
int tmp[200000];
vector<int>G[200000];
void dfs(int v){
    for(int i=0;i<G[v].size();i++){
        if(tmp[G[v][i]]==0){
            tmp[G[v][i]]=-tmp[v];
            dfs(G[v][i]);
        }
    }
}
signed main(){
    int n,a,b;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    tmp[0]=1;
    dfs(0);
    vector<int>odd,even;
    for(int i=0;i<n;i++)
        if(tmp[i]==1)
            odd.push_back(i);
        else
            even.push_back(i);
    int ans[200000];
    vector<int>odd2,even2;
    if(odd.size()<=n/3)
        for(int i=1;i<=n;i++)
            (i%3==0&&i/3<=odd.size()?odd2:even2).push_back(i);
    else if(even.size()<=n/3)
        for(int i=1;i<=n;i++)
            (i%3==0&&i/3<=even.size()?even2:odd2).push_back(i);
    else
        for(int i=1;i<=n;i++)
            (i%3==1||i%3==0&&i/3<=odd.size()-(n+2)/3?odd2:even2).push_back(i);
    for(int i=0;i<odd.size();i++)
        ans[odd[i]]=odd2[i];
    for(int i=0;i<even.size();i++)
        ans[even[i]]=even2[i];
    for(int i=0;i<n;i++)
        cout<<ans[i]<<(i+1==n?'\n':' ');
}