#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vii A(N);
  rep(i,0,N-1){
    int X,Y; cin>>X>>Y;
    A[X-1].pb(Y-1);
    A[Y-1].pb(X-1);
  }
  vi F(N);
  queue<int> Q;
  Q.push(0);
  F[0]=1;
  Q.push(-1);
  int count=0;
  while(Q.size()>1){
    int X=Q.front();
    Q.pop();
    if(X==-1){
      count++;
      Q.push(-1);
    }
    else{
    rep(i,0,A[X].size()){
      int Y=A[X][i];
      if(F[Y]==0){
        F[Y]=3-F[X];
        Q.push(Y);
      }
    }
    }
  }
  vi C(3);
  rep(i,0,N) C[F[i]]++;
  vi D(3);
  rep(i,0,3) D[i]=N/3;
  REP(i,1,N%3) D[i]++;
  if(count<=1||(count==2&&A[0].size()==1)){
    REP(i,1,N) cout<<i<<" ";
    cout<<endl;
  }
  else if(max(0ll,C[1]-D[1])+max(0ll,C[2]-D[2])>D[0]){
    if(max(0ll,C[1]-D[2])+max(0ll,C[2]-D[1])>D[0]){
      if(C[1]-D[1]>D[0]){
        D[0]-=C[2];
        rep(i,0,N){
          if(F[i]==2) F[i]=0;
        }
        int cnt=0;
        rep(i,0,N){
          if(F[i]==1&&cnt<D[0]){
            cnt++;
            F[i]=0;
          }
        }
        cnt=0;
        rep(i,0,N){
          if(F[i]==1&&cnt<D[2]){
            cnt++;
            F[i]=2;
          }
        }
        vi E(3);
        E[0]=1;
        rep(i,0,N){
          cout<<E[F[i]]*3+F[i]<<" ";
          E[F[i]]++;
        }
        cout<<endl;
      }
      else{
        D[0]-=C[1];
        rep(i,0,N){
          if(F[i]==1) F[i]=0;
        }
        int cnt=0;
        rep(i,0,N){
          if(F[i]==2&&cnt<D[0]){
            cnt++;
            F[i]=0;
          }
        }
        cnt=0;
        rep(i,0,N){
          if(F[i]==2&&cnt<D[1]){
            cnt++;
            F[i]=1;
          }
        }
        vi E(3);
       E[0]=1;
       rep(i,0,N){
         cout<<E[F[i]]*3+F[i]<<" ";
         E[F[i]]++;
       }
       cout<<endl;
       }
    }
    else{
      rep(i,0,N) F[i]=3-F[i];
      int cnt1=0,cnt2=0,cnt0=0;
    rep(i,0,N){
      if(F[i]==1){
        if(C[1]-D[1]>cnt1){
          cnt1++;
          cnt0++;
          F[i]=0;
        }
      }
      else{
        if(C[2]-D[2]>cnt2){
          cnt2++;
          cnt0++;
          F[i]=0;
        }
      }
    }
    rep(i,0,N){
      if(F[i]!=0&&cnt0<D[0]){
        F[i]=0;
        cnt0++;
      }
    }
    vi E(3);
    E[0]=1;
    rep(i,0,N){
      cout<<E[F[i]]*3+F[i]<<" ";
      E[F[i]]++;
    }
    cout<<endl;
    }
  }
  else{
    int cnt1=0,cnt2=0,cnt0=0;
    rep(i,0,N){
      if(F[i]==1){
        if(C[1]-D[1]>cnt1){
          cnt1++;
          cnt0++;
          F[i]=0;
        }
      }
      else{
        if(C[2]-D[2]>cnt2){
          cnt2++;
          cnt0++;
          F[i]=0;
        }
      }
    }
    rep(i,0,N){
      if(F[i]!=0&&cnt0<D[0]){
        F[i]=0;
        cnt0++;
      }
    }
    vi E(3);
    E[0]=1;
    rep(i,0,N){
      cout<<E[F[i]]*3+F[i]<<" ";
      E[F[i]]++;
    }
    cout<<endl;
  }
  }



Measured memory_bytes: 16744