#include <bits/stdc++.h>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef vector< vector< vector<ll> > > vvvint;
typedef vector<string> vstring;
typedef vector< vector<string> > vvstring;
typedef vector<char> vchar;
typedef vector< vector<char> > vvchar;
typedef vector<long double> vdouble;
typedef vector< vector<long double> > vvdouble;
typedef vector< vector< vector<long double> > > vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ALL(obj) (obj).begin(), (obj).end()
// #define LLONG_MAX 9223372036854775806
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define MOD 1000000007
// #define MOD 998244353
// #define MOD LLONG_MAX
const double PI=3.14159265358979323846;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }




int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0,};


template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;


void printv(vint &v){
  for(auto e:v) cout<<e<<" ";
  cout<<endl;
}


// 繰り返し二乗法
ll power(ll a, ll b){
  if(a==1)return a;
  // if(a==0)re
  ll res=1;
  while(b>0){
    if(b&1) res=res*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return res;
}

const int MAX=2100000;
 
ll fact[MAX], fact_inv[MAX];
 
void init_fact(ll n){
  fact[0]=1;
  // 階乗の計算
  rep(i, n) fact[i+1]=fact[i]*(i+1)%MOD;
  fact_inv[n]=power(fact[n], MOD-2);
  // 逆元の計算
  for(ll i=n-1;i>=0;i--) fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
}
 
ll comb(ll n, ll r){
  return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
 
ll perm(ll n, ll r){
  return (fact[n]*fact_inv[n-r])%MOD;
}


template< typename G >
struct DoublingLowestCommonAncestor {
  const int LOG;
  vector< int > dep;
  const G &g;
  vector< vector< int > > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector< int >(g.size(), -1));
  }

  void dfs(int idx, int par, int d) {
    table[0][idx] = par;
    dep[idx] = d;
    for(auto &to : g[idx]) {
      if(to != par) dfs(to, idx, d + 1);
    }
  }

  void build() {
    dfs(0, -1, 0);
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = LOG - 1; i >= 0; i--) {
      if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) {
      if(table[i][u] != table[i][v]) {
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }
};




int main() {
  // cout<<fixed<<setprecision(10);

  ll n; cin>>n;
  vint a(n-1),b(n-1);
  rep(i,n-1) {
    cin>>a[i]>>b[i];
    a[i]--; b[i]--;
  }

  UnWeightedGraph g(n);
  rep(i,n-1){
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }

  // DoublingLowestCommonAncestor< UnWeightedGraph > lca(g);
  // lca.build();
  // cout<<lca.query(2,4)<<endl;

  vint ans(n,-1);

  queue<ll> one,two,three;
  rep(i,n){
    ll x = i+1;
    if(x%3==0) three.push(x);
    else if(x%3==1) one.push(x);
    else two.push(x);
  }


  vint vec1(n, -1);
  map<pint, ll> m;
  queue<pint> que;
  que.push(mp(-1, 0));
  vec1[0] = 0;

  ll cnt[] = {0, 0};

  while(!que.empty()){
    ll par, now;
    tie(par, now) = que.front(); que.pop();
    cnt[vec1[now]] ++;

    for(auto to:g[now]){
      if(to == par) continue;
      vec1[to] = (vec1[now] + 1)%2;
      que.push(mp(now, to));
    }
  }

  if(cnt[0] <= n/3){
    rep(i,n){
      if(vec1[i] == 0){
        ll x = three.front(); three.pop();
        ans[i] = x;
      }else{
        ll x;
        if(!two.empty()){
          x = two.front(); two.pop();
        }
        else if(!one.empty()){
          x = one.front(); one.pop();
        }
        else if(!three.empty()){
          x = three.front(); three.pop();
        }
        ans[i] = x;
      }
    }
  }else if(cnt[1] <= n/3){
    rep(i,n){
      if(vec1[i] == 1){
        ll x = three.front(); three.pop();
        ans[i] = x;
      }else{
        ll x;
        if(!two.empty()){
          x = two.front(); two.pop();
        }
        else if(!one.empty()){
          x = one.front(); one.pop();
        }
        else if(!three.empty()){
          x = three.front(); three.pop();
        }
        ans[i] = x;
      }
    }
  }else{
    rep(i,n){
      if(vec1[i] == 0){
        ll x;
        if(!one.empty()){
          x = one.front(); one.pop();
        }
        else if(!three.empty()){
          x = three.front(); three.pop();
        }
        ans[i] = x;
      }else{
        ll x;
        if(!two.empty()){
          x = two.front(); two.pop();
        }
        else if(!three.empty()){
          x = three.front(); three.pop();
        }
        ans[i] = x;
      }
    }
  }


  rep(i,n){
    cout<<ans[i]<<" ";
  }
  cout<<endl;

}






Measured memory_bytes: 23540