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;
int ans[200005];int n;
int a[200005];int cnt;
vector<int>red,bl;
void dfs(int node,vector<int>adj[],int par,int val)
{
  a[node]=val;
  if(val==0)
    red.push_back(node);
  else
    bl.push_back(node);
  for(int j:adj[node])
  {
    if(j!=par)
      dfs(j,adj,node,val^1);
  }
}
int main()
{
//int n;
  cin>>n;
  vector<int>adj[n+1];
  int u,v;
  for(int i=0;i<n-1;i++)
  {
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1,adj,-1,0);
  if(red.size()>bl.size())
  {
    red.clear();
    bl.clear();
    dfs(1,adj,-1,1);
  }
  int p=n/3;
  int x=1,y=2,z=3;
  if(red.size()<=p)
  {
    for(int j:red)
      ans[j]=z,z+=3;
    for(int j:bl)
    {
      if(x<=n)
        ans[j]=x,x+=3;
      else if(y<=n)
        ans[j]=y,y+=3;
      else
        ans[j]=z,z+=3;
    }
  }
  else
  {
    for(int j:red)
    {
      if(x<=n)
        ans[j]=x,x+=3;
      else
        ans[j]=z,z+=3;
    }
    for(int j:bl)
    {
      if(y<=n)
        ans[j]=y,y+=3;
      else if(z<=n)
        ans[j]=z,z+=3;
      else
        ans[j]=x,x+=3;
    }
  }
  for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
  cout<<"\n";
  return 0;
}