#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
namespace tree {
struct Edge {
//	int cost;
//	int id;
};
int n;
vector<Edge> edges;
vector<vector<pair<int, int>>> adj;
void makeTree(int _n) {
	n = _n;
	adj = vector<vector<pair<int, int>>>(n + 1);
	edges.clear();
}
template <typename... T>
int addEdge(int from, int to, const T&... e) {
	int id = edges.size();
	adj[from].emplace_back(to, id);
	adj[to].emplace_back(from, id);
	edges.push_back({e...});
	return id;
}
vector<int> depth, pv, pe, pre, endpre, preseq, siz;
int logn;
vector<vector<int>> anc;
struct Jump {
	int sum;
	void init(int v) {
		Edge& e = edges[pe[v]];
		sum = 1;
	}
	void combine(const Jump& x, const Jump& a) { // a is ancestor of x
		sum = x.sum + a.sum;
	}
};
vector<vector<Jump>> jump;
void dfs(int x, int p = -1) {
	siz[x] = 1;
	pre[x] = preseq.size();
	preseq.push_back(x);
	// Warning: adj order is not the initial order for HLD.
	for (auto& e : adj[x]) {
		int y = e.first, eid = e.second;
		if (y == p) continue;
		depth[y] = depth[x] + 1;
		pv[y] = x;
		pe[y] = eid;
		dfs(y, x);
		siz[x] += siz[y];
	}
	endpre[x] = (int)preseq.size() - 1; // This is the last vertex in the subtree of x
}
void init(int root = 1) {
	siz = vector<int>(n + 1);
	depth = vector<int>(n + 1);
	pv = vector<int>(n + 1, -1);
	pe = vector<int>(n + 1, -1);
	pre = vector<int>(n + 1, -1);
	endpre = vector<int>(n + 1, -1);
	preseq.clear();
	dfs(root);
	logn = 31 - __builtin_clz(n);
	anc = vector<vector<int>>(n + 1, vector<int>(logn + 1));
	for (int i = 1; i <= n; ++i) anc[i][0] = pv[i];
	for (int p = 1; p <= logn; ++p)
		for (int i = 1; i <= n; ++i)
			anc[i][p] = anc[i][p - 1] == -1 ? -1 : anc[anc[i][p - 1]][p - 1];
//	jump = vector<vector<Jump>>(n + 1, vector<Jump>(logn + 1));
//	for (int i = 1; i <= n; ++i)
//		if (anc[i][0] != -1) jump[i][0].init(i);
//	for (int p = 1; p <= logn; ++p)
//		for (int i = 1; i <= n; ++i)
//			if (anc[i][p] != -1)
//				jump[i][p].combine(jump[i][p - 1], jump[anc[i][p - 1]][p - 1]);
}
bool isAnc(int a, int b) {
	return pre[a] <= pre[b] && endpre[a] >= endpre[b];
}
int getChildTowards(int a, int sub) {
	int dh = depth[sub] - depth[a] - 1;
	for (int p = logn; p >= 0; --p)
		if (dh & (1 << p)) sub = anc[sub][p];
	return sub;
}
int getLca(int a, int b) {
	if (isAnc(a, b)) return a;
	if (isAnc(b, a)) return b;
	for (int p = logn; p >= 0; --p)
		if (anc[a][p] != -1 && !isAnc(anc[a][p], b))
			a = anc[a][p];
	a = anc[a][0];
	return a;
}
// Jump up from a to ancestor, running f on each 2^k-block in order.
void jumpUp(int a, int ancestor, function<void(Jump&)> f) {
	assert(isAnc(ancestor, a));
	int up = depth[a] - depth[ancestor];
	for (int p = logn; p >= 0; --p)
		if (up & (1 << p)) {
			f(jump[a][p]);
			a = anc[a][p];
		}
}
vector<int> chainRoot, chainBottom;
void dfsSiz(int x, int p = -1) {
	for (auto it = adj[x].begin(); it != adj[x].end(); ++it)
		if (it->first == p) {
			adj[x].erase(it);
			break;
		}
	siz[x] = 1;
	for (auto& e : adj[x]) {
		int y = e.first;
		dfsSiz(y, x);
		siz[x] += siz[y];
		if (siz[y] > siz[adj[x][0].first]) swap(e, adj[x][0]);
	}
}
void dfsHld(int x, int hldroot) {
	chainRoot[x] = hldroot;
	chainBottom[hldroot] = x;
	for (auto& e : adj[x]) {
		int y = e.first;
		dfsHld(y, y == adj[x][0].first ? hldroot : y);
	}
}
struct Chain {
	vector<int> vs;
	// Bottom vertex and top vertex of chain
	void init(int bot, int top) {
		vs.clear();
		for (int x = bot; x != pv[top]; x = pv[x])
			vs.push_back(x);
	}
};
vector<Chain> chains;
// Move upwards from x to y (ancestor)
// A segment consists of vertices on a heavy path. pre[x] stores the position in the
// heavy-light segment tree of the edge (x, parent[x]).
// Smaller pre -> higher up in tree (lower depth)
// Apply f(Chain, vertex_bottom, vertex_top) on some prefix of the chain
void moveUp(int x, int y, function<void(Chain&, int, int)> f) {
	for (;;) {
		int z = chainRoot[x];
		bool isLastChain = z == chainRoot[y];
		f(chains[chainRoot[x]], x, isLastChain ? y : z);
		if (isLastChain) break;
		x = pv[z];
	}
}
// Chains are contiguous substrings of preSeq array.
// Or, we also have a struct Chain in each chainRoot.
void initHld(int root = 1) {
	siz = vector<int>(n + 1);
	dfsSiz(root); // Make adj[x][0] the largest subtree
	init(root); // Now pre and endpre is on the hld sequence
	chainRoot = vector<int>(n + 1);
	chainBottom = vector<int>(n + 1);
	dfsHld(root, root);
	chains = vector<Chain>(n + 1);
	for (int i = 1; i <= n; ++i) {
		if (chainRoot[i] != i) continue;
		chains[i].init(chainBottom[i], i);
	}
}
}; // namespace tree
using namespace tree;
int main() {
	int n;
	scanf("%d", &n);
	makeTree(n);
	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		addEdge(a, b);
	}
	// Assume vertices are 1-indexed
	init();
	int num[2] = {0, 0};
	vector<int> S[3];
	for (int i = 1; i <= n; ++i) {
		if (depth[i] & 1) ++num[1];
		else ++num[0];
		S[i % 3].push_back(i);
	}
	int p = num[0] > num[1];
	auto take = [&](int x) {
		if (S[x].empty()) return -1;
		int t = S[x].back();
		S[x].pop_back();
		return t;
	};
	vector<int> ans(n + 1, -1);
	if (S[0].size() >= num[p]) {
		for (int i = 1; i <= n; ++i) {
			if (depth[i] % 2 == p) ans[i] = take(0);
		}
	} else {
		for (int i = 1; i <= n; ++i) {
			int v = take(1 + depth[i] % 2);
			ans[i] = v;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (ans[i] == -1) ans[i] = take(0);
		if (ans[i] == -1) ans[i] = take(1);
		if (ans[i] == -1) ans[i] = take(2);
		printf("%d ", ans[i]);
	}
}


Measured memory_bytes: 43580