#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int n, a[200010], b[200010];
vector<int> g[200010];
int dis[200010];
int gr[200010];
int color[200010];
int ans[200010];
vector<int> w, br;
void dfs(int x, int y, int z) {
  for (int i = 0; i < g[x].size(); i++) {
    if (g[x][i] != y) {
      color[g[x][i]] = z ^ 1;
      dfs(g[x][i], x, z ^ 1);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &a[i], &b[i]);
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  dfs(1, 0, 0);
  for (int i = 1; i <= n; i++) {
    if (color[i]) {
      br.push_back(i);
    } else {
      w.push_back(i);
    }
  }
  vector<int> v[3];
  for (int i = 0; i < 3; i++) {
    v[i].clear();
  }
  if (w.size() <= n / 3) {
    for (int i = 0; i < w.size(); i++) {
      v[2].push_back(w[i]);
    }
    for (int i = 0; i < br.size(); i++) {
      if (i < (n + 2) / 3) {
        v[0].push_back(br[i]);
      } else if (i < (n + 2) / 3 + (n + 1) / 3) {
        v[1].push_back(br[i]);
      } else {
        v[2].push_back(br[i]);
      }
    }
  } else if (br.size() <= n / 3) {
    for (int i = 0; i < br.size(); i++) {
      v[2].push_back(br[i]);
    }
    for (int i = 0; i < w.size(); i++) {
      if (i < (n + 2) / 3) {
        v[0].push_back(w[i]);
      } else if (i < (n + 2) / 3 + (n + 1) / 3) {
        v[1].push_back(w[i]);
      } else {
        v[2].push_back(w[i]);
      }
    }
  } else if (w.size() == (n + 2) / 3) {
    for (int i = 0; i < w.size(); i++) {
      v[0].push_back(w[i]);
    }
    for (int i = 0; i < br.size(); i++) {
      if (i < (n + 1) / 3) {
        v[1].push_back(br[i]);
      } else {
        v[2].push_back(br[i]);
      }
    }
  } else if (br.size() == (n + 2) / 3) {
    for (int i = 0; i < br.size(); i++) {
      v[0].push_back(br[i]);
    }
    for (int i = 0; i < w.size(); i++) {
      if (i < (n + 1) / 3) {
        v[1].push_back(w[i]);
      } else {
        v[2].push_back(w[i]);
      }
    }
  } else if (w.size() >= br.size()) {
    for (int i = 0; i < w.size(); i++) {
      if (i < (n + 2) / 3) {
        v[0].push_back(w[i]);
      } else {
        v[2].push_back(w[i]);
      }
    }
    for (int i = 0; i < br.size(); i++) {
      if (i < (n + 1) / 3) {
        v[1].push_back(br[i]);
      } else {
        v[2].push_back(br[i]);
      }
    }
  } else {
    for (int i = 0; i < br.size(); i++) {
      if (i < (n + 2) / 3) {
        v[0].push_back(br[i]);
      } else {
        v[2].push_back(br[i]);
      }
    }
    for (int i = 0; i < w.size(); i++) {
      if (i < (n + 1) / 3) {
        v[1].push_back(w[i]);
      } else {
        v[2].push_back(w[i]);
      }
    }
  }
  /*if (v[0].size() - v[2].size() == 0 && v[1].size() - v[2].size() == 0 ||
      v[0].size() - v[2].size() == 1 && v[1].size() - v[2].size() == 0 ||
      v[0].size() - v[2].size() == 1 && v[1].size() - v[2].size() == 1)
    ;
  else {
    printf("%d\n", 1 / 0);
  }*/
  for (int i = 0; i < n; i++) {
    ans[v[i % 3][i / 3]] = i + 1;
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  printf("\n");
}

Measured memory_bytes: 25332