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;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

int N;
vector<vector<int>> G(202020);
int cnt[2],col[202020],ans[202020];
int num[3],sum[3];

void dfs(int v,int p,int d){
  cnt[d%2]++;
  col[v]=d%2;
  for(int u:G[v]){
    if(u==p) continue;
    dfs(u,v,d+1);
  }
}

void solve(int x){
  rep(i,N){
    int j=col[i];
    if(j==x){
      ans[i]=3*sum[2]+3;
      sum[2]++;
    }else{
      rep(k,3){
        if(sum[k]<num[k]){
          ans[i]=3*sum[k]+k+1;
          sum[k]++;
          break;
        }
      }
    }
  }
}

int main(){
  cin>>N;
  rep(i,N-1){
    int A,B; cin>>A>>B; A--,B--;
    G[A].push_back(B);
    G[B].push_back(A);
  }
  dfs(0,-1,0);
  
  num[0]=N/3+(N%3>0);
  num[1]=N/3+(N%3==2);
  num[2]=N/3;
  
  if(cnt[0]<=N/3) solve(0);
  else if(cnt[1]<=N/3) solve(1);
  else{
    rep(i,N){
      int j=col[i];
      if(sum[j]<num[j]){
        ans[i]=3*sum[j]+j+1;
        sum[j]++;
      }else{
        ans[i]=3*sum[2]+3;
        sum[2]++;
      }
    }
  }
  rep(i,N) cout<<ans[i]<<" ";
  cout<<endl;
  return 0;
}