#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>

using ll = long long int;
using namespace std;

// make rooted tree from tree gragh G
// G_rooted[i]: set of child nodes of i-th node
// par[i] becomes the index of parent of i-th node
int make_rooted_tree(std::vector<std::vector<long long int> > &G, long long int N, long long int root_index, std::vector<std::vector<long long int> > &G_rooted, std::vector<long long int> &par);
// subroutine of make_rooted_tree must not be called in other places
int sub_make_rooted_tree(std::vector<std::vector<long long int> > &G, long long int N, long long int root_index, std::vector<std::vector<long long int> > &G_rooted, std::vector<long long int> &par);

// calculate depth: distance from root for each node
int calculate_depth(std::vector<std::vector<long long int> > &G_rooted, long long int N, long long int root_index, std::vector<long long int> &depth);
int sub_calculate_depth(std::vector<std::vector<long long int> > &G_rooted, long long int N, long long int index, std::vector<long long int> &depth, long long int depth_tmp);

int main(){
  
  // read problem
  ll N, tmp1, tmp2, tmp3;
  cin >> N;
  vector<vector<ll> > G(N);
  for(ll i = 0; i < N-1; i++){
    cin >> tmp1 >> tmp2;
    G[tmp1-1].push_back(tmp2-1);
    G[tmp2-1].push_back(tmp1-1);
  }

  // solve problem
  vector<vector<ll> > G_rooted(N);
  vector<ll> parent(N);

  make_rooted_tree(G, N, 0, G_rooted, parent);

  vector<ll> depth(N);
  calculate_depth(G_rooted, N, 0, depth);

  ll N_even = 0, N_odd = 0;
  for(ll i = 0; i < N; i++){
    if((depth[i]+2)%2 == 0){
      N_even++;
    }
    else{
      N_odd++;
    }
  }

  //ll tmp_array[3] = {2,1,3};
  ll N1 = (N+2)/3, N2 = (N+1)/3, N3 = N/3;

  vector<ll> ans_array(N), used(N+1);

  // fill all odd-ranked node by multiply of 3
  if(N_odd < N2){
    tmp1 = 3;
    for(ll i = 0; i < N; i++){
      if((depth[i]+2)%2 == 1){
        ans_array[i] = tmp1;
        used[tmp1] = 1;
        tmp1 += 3;
      }
    }
    tmp1 = 1;
    for(ll i = 0; i < N; i++){
      if((depth[i]+2)%2 == 1){
        continue;
      }
      while(used[tmp1] == 1){
        tmp1++;
      }
      ans_array[i] = tmp1;
      used[tmp1] = 1;
    }
  }
  // fill all even-ranked node by multiply of 3
  else if(N_even < N2){
    tmp1 = 3;
    for(ll i = 0; i < N; i++){
      if((depth[i]+2)%2 == 0){
        ans_array[i] = tmp1;
        used[tmp1] = 1;
        tmp1 += 3;
      }
    }
    tmp1 = 1;
    for(ll i = 0; i < N; i++){
      if((depth[i]+2)%2 == 0){
        continue;
      }
      while(used[tmp1] == 1){
        tmp1++;
      }
      ans_array[i] = tmp1;
      used[tmp1] = 1;
    }
  }
  // general cases
  else if(N_even <= N_odd){
    tmp1 = 1;
    tmp2 = 2;
    tmp3 = 3;
    for(ll i = 0; i < N; i++){
      // odd
      if((depth[i]+2)%2 == 1){
        if(tmp1 <= N){
          ans_array[i] = tmp1;
          tmp1 += 3;
        }
        else{
          ans_array[i] = tmp3;
          tmp3 += 3;
        }
      }
      // even
      else{ //if((depth[i]+2)%2 == 0){
        if(tmp2 <= N){
          ans_array[i] = tmp2;
          tmp2 += 3;
        }
        else{
          ans_array[i] = tmp3;
          tmp3 += 3;
        }
      }
    }

  }
  // other cases
  else{// if(N_even > N_odd){
    tmp1 = 1;
    tmp2 = 2;
    tmp3 = 3;
    for(ll i = 0; i < N; i++){
      // odd
      if((depth[i]+2)%2 == 0){
        if(tmp1 <= N){
          ans_array[i] = tmp1;
          tmp1 += 3;
        }
        else{
          ans_array[i] = tmp3;
          tmp3 += 3;
        }
      }
      // even
      else{ //if((depth[i]+2)%2 == 1){
        if(tmp2 <= N){
          ans_array[i] = tmp2;
          tmp2 += 3;
        }
        else{
          ans_array[i] = tmp3;
          tmp3 += 3;
        }
      }
    }

  }
/*
  for(ll i = 0; i < N; i++){
    // odd
    if(depth[i]&1){
      if(tmp_array[1] <= N){
        ans_array[i] = tmp_array[1];
        tmp_array[1] += 3;
      }
      else{
        ans_array[i] = tmp_array[2];
        tmp_array[2] += 3;
      }
    }
    // even
    else{// if(depth[i]&1 == 0)
      if(tmp_array[0] <= N){
        ans_array[i] = tmp_array[0];
        tmp_array[0] += 3;
      }
      else{
        ans_array[i] = tmp_array[2];
        tmp_array[2] += 3;
      }
    }
  }*/

  cerr << "Answer: " << endl;
  for(ll i = 0; i < N; i++){
    //cout << ans_array[i] << " ";
    printf("%lld ", ans_array[i]);
  }cerr << endl;

  return 0;

}



int make_rooted_tree(std::vector<std::vector<long long int> > &G, long long int N, long long int root_index, std::vector<std::vector<long long int> > &G_rooted, std::vector<long long int> &par){
  // initialize par and call sub_make_rooted_tree
  par[root_index] = root_index;
  sub_make_rooted_tree(G, N, root_index, G_rooted, par);

  return 0;
}

int sub_make_rooted_tree(std::vector<std::vector<long long int> > &G, long long int N, long long int root_index, std::vector<std::vector<long long int> > &G_rooted, std::vector<long long int> &par){

  for(long long int i = 0; i < G[root_index].size(); i++){
    // for all connected nodes but parent node
    if(G[root_index][i] != par[root_index]){
      par[G[root_index][i]] = root_index;
      G_rooted[root_index].push_back(G[root_index][i]);
      sub_make_rooted_tree(G, N, G[root_index][i], G_rooted, par);
    }
  }

  return 0;
}

int calculate_depth(std::vector<std::vector<long long int> > &G_rooted, long long int N, long long int root_index, std::vector<long long int> &depth){
  depth[root_index] = 0;
  for(long long int i = 0; i < G_rooted[root_index].size(); i++){
    sub_calculate_depth(G_rooted, N, G_rooted[root_index][i], depth, 1);
  }

  return 0;
}

int sub_calculate_depth(std::vector<std::vector<long long int> > &G_rooted, long long int N, long long int index, std::vector<long long int> &depth, long long int depth_tmp){

  depth[index] = depth_tmp;
  for(long long int i = 0; i < G_rooted[index].size(); i++){
    sub_calculate_depth(G_rooted, N, G_rooted[index][i], depth, depth_tmp+1);
  }

  return 0;
}


Measured memory_bytes: 36992