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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

class Tree{
  private:
    ll V;
    vvll Path;
    map<pll, ll> dist_map;
    vll depth;
    vll dist_from_root;
    vvll par;
    ll diameter;
    vll diameter_pair;
    ll radius;
    vll radius_pair;
    ll num_of_center_of_gravities;
    vll center_of_gravities;

    void search(ll pos, ll depth_tmp, ll dist_tmp){
      depth[pos] = depth_tmp;
      dist_from_root[pos] = dist_tmp;
      for(int i=0; i<Path[pos].size(); ++i){
        ll next = Path[pos][i];
        if(depth[next]>=0) continue;
        search(next, depth_tmp+1, dist_tmp+dist_map[make_pair(pos, next)]);
      }
      return;
    }

    void search_par_zero(ll root){
      for(int i=0; i<Path[root].size(); ++i){
        ll next = Path[root][i];
        if(par[next].size()>0) continue;
        par[next].push_back(root);
        search_par_zero(next);
      }
      return;
    }

    void search_par(void){
      ll size_tmp = par[0].size();
      for(int i=0; i<V; ++i){
        par[i].push_back(par[par[i][size_tmp-1]][size_tmp-1]);
      }
      return;
    }

  public:
    Tree(ll V_){
      V = V_;
      Path.resize(V);
      depth.resize(V, -1);
      par.resize(V);
      dist_from_root.resize(V, -1);
      diameter = -1;
      radius = -1;
      num_of_center_of_gravities = -1;
      diameter_pair.resize(0);
      radius_pair.resize(0);
      center_of_gravities.resize(0);
      return;
    };

    ~Tree(void){
      return;
    };

    void add(ll x, ll y, ll dist=1){
      Path[x].push_back(y);
      Path[y].push_back(x);
      dist_map.insert(make_pair(make_pair(x, y), dist));
      dist_map.insert(make_pair(make_pair(y, x), dist));
      diameter = -1;
      radius = -1;
      num_of_center_of_gravities = -1;
      return;
    };

    void set_root(ll root){
      for(int i=0; i<V; ++i) depth[i]=-1;
      search(root, 0, 0);

      par[root].push_back(root);
      search_par_zero(root);
      ll par_num = 1;
      while(par_num<=V){
        search_par();
        par_num*=2;
      }
      return;
    }

    ll LCA(ll x, ll y){
      if(depth[x]!=depth[y]){
        if(depth[x]<depth[y]) swap(x,y);
        ll depth_diff = depth[x]-depth[y];
        ll tmp = 0;
        while(depth_diff>0){
          if(depth_diff%2) x = par[x][tmp];
          depth_diff/=2;
          tmp++;
        }
      }
      if(depth[x]!=depth[y]){
        fprintf(stderr, "depth x != depth y : %lld != %lld\n", depth[x], depth[y]);
        exit(0);
      }

      if(x==y) return x;

      ll tmp = par[x].size()-1;
      while(tmp>=0){
        if(par[x][tmp]!=par[y][tmp]){
          x = par[x][tmp];
          y = par[y][tmp];
        }
        tmp--;
      }
      if(par[x][0]!=par[y][0]){
        fprintf(stderr, "par x != par y : %lld %lld\n", par[x][0], par[y][0]);
        exit(0);
      }

      return par[x][0];
    }

    ll dist(ll x, ll y){
      ll mid = LCA(x, y);
      return dist_from_root[x] + dist_from_root[y] - 2*dist_from_root[mid];
    }

    ll get_diameter(void){
      if(this->diameter>0) return this->diameter;
      vll flag(V, true);
      vll front_points;
      front_points.push_back(0);
      flag[0] = false;
      while(true){
        vll front_points_copy = front_points;
        front_points.clear();
        for(auto x : front_points_copy){
          for(auto y : Path[x]){
            if(!flag[y]) continue;
            front_points.push_back(y);
            flag[y] = false;
          }
        }
        if(front_points.size()==0){
          front_points = front_points_copy;
          break;
        }
      }

      flag.assign(V, true);
      ll u = front_points[0];
      front_points.clear();
      front_points.push_back(u);
      flag[u] = false;
      ll d = 0;
      while(true){
        vll front_points_copy = front_points;
        front_points.clear();
        for(auto x : front_points_copy){
          for(auto y : Path[x]){
            if(!flag[y]) continue;
            front_points.push_back(y);
            flag[y] = false;
          }
        }
        if(front_points.size()==0){
          front_points = front_points_copy;
          break;
        }
        d++;
      }
      ll v = front_points[0];

      this->diameter = d;
      this->diameter_pair.push_back(u);
      this->diameter_pair.push_back(v);

      return d;
    };
    
    vll get_diameter_pair(void){
      if(this->diameter<=0){
        get_diameter();
      }
      return this->diameter_pair;
    };

    ll get_radius(void){
      if(radius>0) return radius;

      vll leaves;
      vll connects(V);
      for(ll i=0; i<V; ++i){
        connects[i]=Path[i].size();
        if(connects[i]==1) leaves.push_back(i);
      }

      ll r=0;
      while(true){
        vll leaves_copy = leaves;
        leaves.clear();
        for(auto x : leaves_copy){
          connects[x] = 0;
          for(auto y : Path[x]){
            connects[y]--;
            if(connects[y]==1) leaves.push_back(y);
          }
        }
        if(leaves.size()==0){
          leaves = leaves_copy;
          if(leaves_copy.size()==2){
            r++;
          }
          break;
        }

        r++;
      }

      this->radius = r;
      this->radius_pair = leaves;

      return radius;
    };

    vll get_radius_pair(void){
      if(this->radius<=0){
        get_radius();
      }
      return this->radius_pair;
    };

    ll getsize(ll x, vll& flag){
      flag[x] = false;
      ll ans = 1;
      for(auto y : Path[x]){
        if(!flag[y]) continue;
        ans += getsize(y, flag);
      }
      return ans;
    };

    ll get_num_of_center_of_gravities(void){
      if(this->num_of_center_of_gravities>0) return this->num_of_center_of_gravities;
      ll v=0;
      ll max_size = V;
      ll counter = 0;
      vll c_of_g;
      while(true){
        ll max_size = -1;
        ll next_v = -1;
        vll flag(V, true);
        flag[v] = false;
        for(auto y : Path[v]){
          ll y_size = getsize(y, flag);
          if(max_size < y_size){
            max_size = y_size;
            next_v = y;
          }
        }
        if(max_size<=V/2){
          counter++;
          c_of_g.push_back(v);
          if(counter>=2) break;
        }else if(counter>0){
          break;
        }
        v = next_v;
      }

      this->num_of_center_of_gravities = c_of_g.size();
      this->center_of_gravities = c_of_g;
      return this->num_of_center_of_gravities;
    };

    vll get_center_of_gravities(void){
      if(this->num_of_center_of_gravities<=0) get_num_of_center_of_gravities();
      return this->center_of_gravities;
    }
};

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  IN(N);
  Tree tree(N);
  vll a(N-1), b(N-1);
  REP(i,N-1){
    IN(a[i], b[i]);
    a[i]--; b[i]--;
    tree.add(a[i], b[i]);
  }

  tree.set_root(0);

  vll C(N, -1);
  REP(i,N){
    debug_print(i);
    ll d = tree.dist(0,i);
    debug_print(d);
    if(d%2==0) C[i]=0;
    else       C[i]=1;
  }

  ll C_zero=0, C_one=0;
  REP(i,N){
    if(C[i]==0) C_zero++;
    else        C_one++;
  }

  vll ans(N, -1);
  ll zero=1;
  ll one=0;
  ll two=0;

  if(C_zero<=N/3){
    REP(i,N){
      if(C[i]==0){
        ans[i]=3*zero;
        zero++;
      }else{
        if(3*one+1<=N){
          ans[i]=3*one+1;
          one++;
        }else if(3*two+2<=N){
          ans[i]=3*two+2;
          two++;
        }else{
          ans[i]=3*zero;
          zero++;
        }
      }
    }
  }else if(C_one<=N/3){
    REP(i,N){
      if(C[i]==1){
        ans[i]=3*zero;
        zero++;
      }else{
        if(3*one+1<=N){
          ans[i]=3*one+1;
          one++;
        }else if(3*two+2<=N){
          ans[i]=3*two+2;
          two++;
        }else{
          ans[i]=3*zero;
          zero++;
        }
      }
    }
  }else{
    REP(i,N){
      if(C[i]==0){
        if(3*one+1<=N){
          ans[i]=3*one+1;
          one++;
        }else{
          ans[i]=3*zero;
          zero++;
        }
      }else{
        if(3*two+2<=N){
          ans[i]=3*two+2;
          two++;
        }else{
          ans[i]=3*zero;
          zero++;
        }
      }
    }
  }

  REP(i,N){
    printf("%lld ", ans[i]);
  }
  printf("\n");


  return 0;
}

Measured memory_bytes: 108160