#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

template<typename CostType>
/// \brief 辺の情報
struct Edge{
  int      to;
  CostType cost;

  Edge(int t, CostType c): to(t), cost(c){
  }
};

template<typename CostType>
class Graph{

private:

  /// \brief adjacent_list_[n]=ノードnの隣接リストを表すvector<Edge>
  std::vector<std::vector<Edge<CostType>>> adjacent_list_;

public:

  /// \brief 頂点数
  const int NODE_SIZE_;

  /// \brief コンストラクタ
  /// \param node_size 頂点数
  explicit Graph(const int node_size): NODE_SIZE_(node_size),
                                       adjacent_list_(node_size){
  }

  /// \brief 有向グラフの辺を生やす
  /// \param from 辺の根本の頂点の番号
  /// \param to 辺の先の頂点の番号
  /// \param cost 辺のコスト
  void SetDirectedEdge(const int from, const int to, const CostType cost){
    adjacent_list_[from].push_back(Edge<CostType>(to, cost));
  }

  /// \brief 無向グラフの辺を生やす
  /// \param node_a 一方の頂点の番号
  /// \param node_b もう一方の頂点の番号
  /// \param cost 辺のコスト
  void
  SetUndirectedEdge(const int node_a, const int node_b, const CostType cost){
    SetDirectedEdge(node_a, node_b, cost);
    SetDirectedEdge(node_b, node_a, cost);
  }

  /// \brief ある頂点の隣接リストを取得
  /// \param node_num 頂点の番号
  /// \return 隣接リスト
  std::vector<Edge<CostType>> GetAdjacentList(int node_num) const{
    return adjacent_list_[node_num];
  }
};

void DFS(Graph<int>& graph, int curr,int prev,vector<int>& node_type,bool is_one){
  if(is_one){
    node_type[curr]=1;
  }else{
    node_type[curr]=2;
  }
  for(auto e:graph.GetAdjacentList(curr)){
    if(e.to!=prev){
      DFS(graph,e.to,curr,node_type,!is_one);
    }
  }
}

void Solve(Graph<int>& graph, bool start_one,int n){
  vector<int> node_type(n+1);
  DFS(graph,1,-1,node_type,start_one);

  int limit_sum=n;



  int three_count_limit=n/3;
  limit_sum-=three_count_limit;
  int two_count_limit=limit_sum/2;
  limit_sum-=two_count_limit;
  int one_count_limit=limit_sum;


  int one_count=0,two_count=0,three_count=0;
  for(auto v:node_type){
    if(v==0) continue;
    if(v==1){
      one_count++;
    }else{
      two_count++;
    }
  }
  vector<int> result(n+1);
  std::unordered_set<int> unused_val;
  for(int i=1;i<=n;i++){
    unused_val.insert(i);
  }
  if(one_count<=one_count_limit){
    int val_1=3;
    for(int i=1;i<=n;i++){
      if(node_type[i]==1){
        result[i]=val_1;
        unused_val.erase(val_1);
        val_1+=3;
      }
    }
    for(int i=1;i<=n;i++){
      if(node_type[i]==2){
        int next=*unused_val.begin();
        result[i]=next;
        unused_val.erase(next);
        if(unused_val.empty()) break;
      }
    }

  }else if(two_count<two_count_limit){
    int val_1=3;
    for(int i=1;i<=n;i++){
      if(node_type[i]==2){
        result[i]=val_1;
        unused_val.erase(val_1);
        val_1+=3;
      }
    }
    for(int i=1;i<=n;i++){
      if(node_type[i]==1){
        int next=*unused_val.begin();
        result[i]=next;
        unused_val.erase(next);
        if(unused_val.empty()) break;
      }
    }
  }else{
    int val_1=1,val_2=2;
    for(int i=1;i<=n;i++){
      if(node_type[i]==1){
        result[i]=val_1;
        unused_val.erase(val_1);
        val_1+=3;
        if(val_1>n) break;
      }
    }
    for(int i=1;i<=n;i++){
      if(node_type[i]==2){
        result[i]=val_2;
        unused_val.erase(val_2);
        val_2+=3;
        if(val_2>n) break;
      }
    }
    for(int i=1;i<=n;i++){
      int next=*unused_val.begin();
      if(result[i]==0){
        result[i]=next;
        unused_val.erase(next);
        if(unused_val.empty()) break;
      }
    }
  }
  for(int i=1;i<=n;i++){
    cout<<result[i];
    if(i==n) cout<<endl;
    else cout<<" ";
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n;
  cin>>n;
  Graph<int> graph(n+1);
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    graph.SetUndirectedEdge(a,b,1);
  }

  if(n==2){
    cout<<"1 2"<<endl;
    return 0;
  }

  Solve(graph,true,n);




  return 0;
}




Measured memory_bytes: 29480