#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, std::vector<long long> a, std::vector<long long> b){
  vector<vector<ll>> tree(N);
  REP(N-1){
    tree[a[i]].push_back(b[i]);
    tree[b[i]].push_back(a[i]);
  }
  vector<ll> ans(N);
  vector<ll> flag(N,0);
  deque<ll> q;
  q.push_back(0);
  flag[0]=1;
  map<ll,ll> cnt;
  cnt[-1]=cnt[1]=0;
  while(!q.empty()){
    ll tmp=q.front();q.pop_front();
    ++cnt[flag[tmp]];
    for (auto &&j : tree[tmp])
    {
      if(flag[j]==0){
        flag[j]=-flag[tmp];
        q.push_back(j);
      }
    }
  }
  dump(flag);
  bool swapf=false;
  if(cnt[1]<cnt[-1]){
    swap(cnt[1],cnt[-1]);
    swapf=true;
  }
  if(cnt[-1]<=N/3){
    ll three=3,other=1;
    set<ll> s;
    REP(N){
      s.insert(i+1);
    }
    REP(N){
      if(flag[i]==(swapf?1:-1)){
        ans[i]=three;
        s.erase(three);
        three+=3;
      }
    }
    vector<ll> ss(s.begin(),s.end());
    ll itr=0;
    REP(N){
      if(flag[i]!=(swapf?1:-1)){
        ans[i]=ss[itr];
        ++itr;
      }
    }
  }else{
    ll one=1,two=2,three=3;
    REP(N){
      if(flag[i]==1){
        if(two>N){
          ans[i]=three;
          three+=3;
        }else{
          ans[i]=two;
          two+=3;
        }
      }else{
        if(one>N){
          ans[i]=three;
          three+=3;
        }else{
          ans[i]=one;
          one+=3;
        }
      }
    }
  }
  REP(N){
    cout<<ans[i]<<" ";
  }
  cout<<endl;
}

int main(){
  cout<<setprecision(1000);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N-1);
    std::vector<long long> b(N-1);
    for(int i = 0 ; i < N-1 ; i++){
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
        --a[i];--b[i];
    }
    solve(N, std::move(a), std::move(b));
    return 0;
}


Measured memory_bytes: 22988