#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 998244353;
const int MAXN =(int) 2e5+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
int N;
vector<int> G[MAXN];
int x,y,z,cnt;
int ans[MAXN];

void DFS(int u,int fa,int dep){
    if(dep){
        if(x<=N){
            ans[u]=x;
            x+=3;
        }
        else{
            ans[u]=z;
            z+=3;
        }
    }
    else{
        if(y<=N){
            ans[u]=y;
            y+=3;
        }
        else{
            ans[u]=z;
            z+=3;
        }
    }
    int sizu=G[u].size();
    for(int i=0;i<sizu;i++){
        int v=G[u][i];
        if(v==fa) continue;
        DFS(v,u,dep^1);
    }
}

void DFS1(int u,int fa,int dep){
    int sizu=G[u].size();
    if(dep) cnt++;
    for(int i=0;i<sizu;i++){
        int v=G[u][i];
        if(v==fa) continue;
        DFS1(v,u,dep^1);
    }
}

void DFS2(int u,int fa,int dep){
    if(dep){
        ans[u]=z;
        z+=3;
    }
    else{
        if(x<=N){
            ans[u]=x;
            x+=3;
        }
        else if(y<=N){
            ans[u]=y;
            y+=3;
        }
        else{
            ans[u]=z;
            z+=3;
        }
    }
    int sizu=G[u].size();
    for(int i=0;i<sizu;i++){
        int v=G[u][i];
        if(v==fa) continue;
        DFS2(v,u,dep^1);
    }
}

void work(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        int u,v; scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    x=1,y=2,z=3,cnt=0;
    DFS1(1,-1,1);
//    printf("cnt = %d\n",cnt);
    int cnt1=N-cnt;
    if(cnt>N/3&&cnt1>N/3){
        DFS(1,-1,1);
    }
    else{
        int root=1;
        if(cnt1<=N/3) root=G[1][0];
        DFS2(root,-1,1);
    }
    for(int i=1;i<=N;i++){
        printf("%d",ans[i]);
        if(i==N) printf("\n");
        else printf(" ");
    }
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}





Measured memory_bytes: 20864