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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
vector<ll> node[200005];
ll ans[200005]={0};
bool used[200005]={0};
void dfs(ll pos,ll num){
  ans[pos]=num;
  num++;
  num%=2;
  for(int i=0;i<node[pos].size();i++){
    ll to=node[pos][i];
    if(!used[to]){
      used[to]=true;
      dfs(to,num);
    }
  }
}
int main(){
  ll n;
  cin>>n;
  for(int i=1;i<n;i++){
    ll s,t;
    cin>>s>>t;
    node[s].push_back(t);
    node[t].push_back(s);
  }
  for(int i=1;i<=n;i++) used[i]=false;
  used[1]=true;
  dfs(1,0);

  ll n1=0,n2=0;
  for(int i=1;i<=n;i++){
    if(ans[i]==0) n1++;
    else n2++;
  }
  if(n1<n2){
    for(int i=1;i<=n;i++) ans[i]^=1;
    swap(n1,n2);
  }
  if(n2*3+1<n){
    ll a=3;
    for(int i=1;i<=n;i++){
      if(ans[i]==1) {
        ans[i]=a;
        a+=3;
      }
    }
    ll mb=a;
    a=1;
    for(int i=1;i<=n;i++){
      if(ans[i]==0||ans[i]==1){
        ans[i]=a;
        a++;
        if(a%3==0&&a<mb) a++;
      }
    }
  }
  else{
    ll a=1,b=2,c=3;
    for(int i=1;i<=n;i++){
      if(ans[i]==0){
        if(a<=n){
          ans[i]=a;
          a+=3;
        }
        else{
          ans[i]=c;
          c+=3;
        }
      }
      else{
        if(b<=n){
          ans[i]=b;
          b+=3;
        }
        else{
          ans[i]=c;
          c+=3;
        }
      }
    }
  }
  for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
  cout<<endl;
}