#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int n;
vi dist(vvi& g, int s) {
  vi d(n, -1);
  d[s] = 0;
  deque<int> que = {s};
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    for (int v : g[u]) {
      if (d[v] != -1) { continue; }
      d[v] = d[u] + 1;
      que.push_back(v);
    }
  }
  return d;
}

vi diameter(vvi& g) {
  auto d = dist(g, 0);
  auto max_idx = max_element(all(d)) - d.begin();
  d = dist(g, max_idx);
  vi ret;
  ret.push_back(*(max_element(all(d))));
  ret.push_back(max_idx);
  return ret;
}

void print_(vi& ans) {
  rep (i, n) {
    printf("%d%c", ans[i], " \n"[i == n-1]);
  }
  exit(0);
}

int main() {
  scan(n);
  vvi g(n);
  rep (i, n-1) {
    int a, b;
    scan(a, b);
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  auto dia = diameter(g);
  if (dia[0] <= 2) {
    vi ans(n);
    iota(all(ans), 1);
    print_(ans);
  }

  vi depth(n, -1);
  depth[0] = 0;
  deque<int> que = {0};
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    for (auto v : g[u]) {
      if (depth[v] != -1) {
        continue;
      }
      depth[v] = depth[u] + 1;
      que.push_back(v);
    }
  }
  vvi idx(2);
  rep (i, n) {
    idx[depth[i] % 2].push_back(i);
  }
  vi sz(2);
  rep (i, 2) {
    sz[i] = idx[i].size();
  }
  if (sz[0] < sz[1]) {
    swap(sz[0], sz[1]);
    swap(idx[0], idx[1]);
  }
  debug(idx);

  vvi pool(3);
  FOR (i, 1, n+1) {
    pool[i % 3].push_back(i);
  }
  vi ans(n);
  vi priority0, priority1;
  if (sz[1] <= n / 3) {
    priority1 = {0};
    priority0 = {0, 1, 2};
  } else {
    priority1 = {2, 0};
    priority0 = {1, 0};
  }
  for (int i : idx[1]) {
    for (auto pr : priority1) {
      if (!pool[pr].empty()) {
        ans[i] = pool[pr].back();
        pool[pr].pop_back();
        break;
      }
    }
  }
  for (int i : idx[0]) {
    for (auto pr : priority0) {
      if (!pool[pr].empty()) {
        ans[i] = pool[pr].back();
        pool[pr].pop_back();
        break;
      }
    }
  }
  print_(ans);

  return 0;
}


Measured memory_bytes: 17632