#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using INT = mp::cpp_int;
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll;
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define count2way(v, x) high2way(v, x) - low2way(v, x)
#define lower(v, x) low2way(v, x) - v.begin()       //1番左が0、もし見つから無いならｎを出力
#define higher(v, x) high2way(v, x) - v.begin() - 1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout << a << endl
#define putout2(a, b) \
  putout(a);          \
  putout(b)
#define putout3(a, b, c) \
  putout(a);             \
  putout(b);             \
  putout(c)
#define putout4(a, b, c, d) \
  putout(a);                \
  putout(b);                \
  putout(c);                \
  putout(d)
#define putout5(a, b, c, d, e) \
  putout(a);                   \
  putout(b);                   \
  putout(c);                   \
  putout(d);                   \
  putout(e)
#define Gput(a, b) G[a].push_back(b)
#define cin1(a) cin >> a
#define cin2(a, b) cin >> a >> b
#define cin3(a, b, c) cin >> a >> b >> c
#define cin4(a, b, c, d) cin >> a >> b >> c >> d
#define cin5(a, b, c, d, e) cin >> a >> b >> c >> d >> e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
  if (c >= '0' && c <= '9')
  {
    return c - '0';
  }
  return 0;
}
ll lcm(ll x, ll y)
{
  ll z = gcd(x, y);
  return x * y / z;
}
INT LCM(INT x, INT y)
{
  INT z = gcd(x, y);
  return x * y / z;
}
ll primejudge(ll n)
{
  if (n < 2)
    return 0;
  else if (n == 2)
    return 1;
  else if (n % 2 == 0)
    return 0;
  double sqrtn = sqrt(n);
  Loop(i, 3, sqrtn + 1)
  {
    if (n % i == 0)
    {
      return 0;
    }
    i++;
  }
  return 1;
}
INT modinv(INT a, INT m)
{
  INT b = m, u = 1, v = 0;
  while (b)
  {
    INT t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0)
    u += m;
  return u;
}

int main()
{
  cout << fixed << setprecision(30);
  ll n;
  cin >> n;
  Graph G(n);
  loop(i, n - 1)
  {
    ll a, b;
    cin >> a >> b;
    Gput(a - 1, b - 1);
    Gput(b - 1, a - 1);
  }
  vector<ll> dist(n, -1);
  queue<ll> que;
  dist[0] = 0;
  que.push(0);
  while (!que.empty())
  {
    ll v = que.front();
    que.pop();
    for (ll nextv : G[v])
    {
      if (dist[nextv] != -1)
        continue;
      dist[nextv] = dist[v] + 1;
      que.push(nextv);
    }
  }
  vec red;
  vec blue;
  loop(i, n)
  {
    if (dist[i] % 2 == 1)
      red.push_back(i);
    else
      blue.push_back(i);
  }
  ll r = red.size(), b = blue.size();
  vec ans(n);
  if (r > n / 3 && b > n / 3)
  {
    queue<ll> num;
    Loop(i, 1, n + 1) if (i % 3 == 1) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 0) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 2) num.push(i);
    loop(i, r)
    {
      ans[red[i]] = num.front();
      num.pop();
    }
    loop(i, b)
    {
      ans[blue[i]] = num.front();
      num.pop();
    }
    loop(i, n)
    {
      cout << ans[i];
      if (i != n - 1)
        cout << " ";
    }
    putout("");
    return 0;
  }
  if (r <= n / 3)
  {
    queue<ll> num;
    Loop(i, 1, n + 1) if (i % 3 == 0) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 2) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 1) num.push(i);
    loop(i, r)
    {
      ans[red[i]] = num.front();
      num.pop();
    }
    loop(i, b)
    {
      ans[blue[i]] = num.front();
      num.pop();
    }
    loop(i, n)
    {
      cout << ans[i];
      if (i != n - 1)
        cout << " ";
    }
    putout("");
    return 0;
  }
  if (b <= n / 3)
  {
    queue<ll> num;
    Loop(i, 1, n + 1) if (i % 3 == 0) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 2) num.push(i);
    Loop(i, 1, n + 1) if (i % 3 == 1) num.push(i);
    loop(i, b)
    {
      ans[blue[i]] = num.front();
      num.pop();
    }
    loop(i, r)
    {
      ans[red[i]] = num.front();
      num.pop();
    }
    loop(i, n)
    {
      cout << ans[i];
      if (i != n - 1)
        cout << " ";
    }
    putout("");
    return 0;
  }
}

Measured memory_bytes: 21352