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 ll long long
#define pii pair<int,int>
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
vector<int> g[200005];
vector<int> l,r;
int n;
int ans[200005];
void dfs(int v,int lst,int co){
    if(co) l.pb(v);
    else r.pb(v);
    for(int i=0;i<g[v].size();i++)
        if(g[v][i]!=lst)
            dfs(g[v][i],v,co^1);
}
int main(){
    scanf("%d",&n);
    int on=n/3+(n%3!=0),tw=n/3+(n%3==2),th=n/3;
    for(int i=1;i<=n-1;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,-1,0);
    if(l.size()>r.size()) swap(l,r);
    if(l.size()<=n/3){
        int non=0,ntw=0,nth=0;
        for(int i=0;i<l.size();i++)
            ans[l[i]]=nth*3+3,nth++;
        int i=0;
        while(nth!=th) ans[r[i]]=nth*3+3,nth++,i++;
        while(ntw!=tw) ans[r[i]]=ntw*3+2,ntw++,i++;
        while(non!=on) ans[r[i]]=non*3+1,non++,i++; 
    }
    else{
        int non=0,ntw=0,nth=0;
        int i=0,j=0;
        while(non!=on) ans[l[i]]=non*3+1,non++,i++;
        while(ntw!=tw) ans[r[j]]=ntw*3+2,ntw++,j++;
        while(nth!=th && i<l.size()) ans[l[i]]=nth*3+3,nth++,i++;
        while(nth!=th) ans[r[j]]=nth*3+3,nth++,j++;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    printf("\n");
    return 0;
}