#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define inv(x) Power(x, mod - 2)
#define fi first
#define se second
#define MP make_pair
#define PB push_back

typedef std::vector<int> Poly;
typedef std::pair<int,int> Pair;
typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;

const int maxn = 200000, maxm = 2000, MAX = 1e6 + 5, mod = 1000000;
//template{{{
const long double Pi = 3.14159265358979323846l, Eps = 1e-4;
template <class T> inline bool equal(T x, T y) { return fabs(x - y) < Eps; }
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; };
inline void inc(int &x, int y) { x += y; x -= (x >= mod ? mod : 0); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int Power(int x, int y, int Mod = mod) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = (ll) ans * x % Mod;
		x = (ll) x * x % Mod, y >>= 1;
	} return ans;
}

/*char buf[1<<23],obuf[1<<23],*p1=buf,*p2=buf, *O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void print(int x) {
    if(x > 9) print(x / 10);
    *O++=x%10+'0';
} */

template <class T> inline T	input() {
	T x; char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return flag ? -x : x;
}

template <class T> inline bool chkmin(T &x, T y) { x = x < y ? x : y; return x == y; }
template <class T> inline bool chkmax(T &x, T y) { x = x > y ? x : y; return x == y; }
template <class T> inline T gcd(T x, T y) { return !y ? x : gcd(y, x % y); }
template <class T> inline T sqrm(T x) { return (ll) x * x % mod; }
template <class T> inline T sqr(T x) { return x * x; }

struct {
	inline operator int () { return input<int>(); }
	inline operator long long () { return input<long long>(); }
	template <class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read; //}}}

int n;
int a[maxn + 5];
std::vector<int> T[maxn + 5];
bool mark[maxn + 5], vis[maxn + 5];
int col[maxn + 5];
int cnt0, cnt1;

void bfs() {
	std::queue<int> que;
	que.push(1), vis[1] = true;
	while (!que.empty()) {
		int u = que.front(); que.pop();
		if (mark[u]) ++cnt1;
		else ++cnt0;
		for (int v : T[u]) {
			if (vis[v]) continue;
			mark[v] = mark[u] ^ 1;
			vis[v] = true;
			que.push(v);
		}
	}

	if (cnt0 <= cnt1) return void();
	std::swap(cnt0, cnt1);
	for (int i = 1; i <= n; ++i)
		mark[i] ^= 1;
}

int nxt(int p) { while (vis[++p]); return p; }

signed main() {
#ifdef local
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	freopen("log", "w", stderr);
#endif

	n = read;
	for (int i = 1; i < n; ++i) {
		int x = read, y = read;
		T[x].push_back(y);
		T[y].push_back(x);
	}

	bfs();

	if (cnt0 <= n / 3) {
		memset(vis, 0, sizeof vis);
		for (int i = 1; i <= n; ++i)
			if (!mark[i]) col[i] = 0, vis[i] = true;
		int now, i;
		for (now = 0, i = 1; i <= (n + 2) / 3; ++i)
			now = nxt(now), col[now] = 1, vis[now] = true;
		for (now = 0, i = 1; i <= (n + 1) / 3; ++i)
			now = nxt(now), col[now] = 2, vis[now] = true;
	}

	else {
		for (int i = 1, cnt = 0; i <= n && cnt < (n + 2) / 3; ++i)
			if (mark[i]) col[i] = 1, ++cnt;
		for (int i = 1, cnt = 0; i <= n && cnt < (n + 1) / 3; ++i)
			if (!mark[i]) col[i] = 2, ++cnt;
	}

	int now0 = 3, now1 = 1, now2 = 2;
	for (int i = 1; i <= n; ++i) {
		if (col[i] == 0) printf("%d%c", now0, i == n ? '\n' : ' '), now0 += 3;
		if (col[i] == 1) printf("%d%c", now1, i == n ? '\n' : ' '), now1 += 3;
		if (col[i] == 2) printf("%d%c", now2, i == n ? '\n' : ' '), now2 += 3;
	}
	return 0;
}


Measured memory_bytes: 15220