#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

void Calculate_Depth(vector<vector<int>>&edge, vector<int>&depth, int stnode) {
	depth[stnode] = 0;
	queue<int>Q;
	Q.push(stnode);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (depth[i] > depth[cn] + 1) {
				depth[i] = depth[cn] + 1;
				Q.push(i);
			}
		}
	}
	return;
}

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<vector<int>>edge(N);
	for (int i = 1; i < N; i++) {
		cin >> L >> R;
		L--, R--;
		edge[L].push_back(R);
		edge[R].push_back(L);
	}
	int num = 0;
	for (int i = 0; i < N; i++) {
		if (edge[i].size() != 1)num++;
	}
	if (num <= 1 || N <= 3) {
		for (int i = 1; i <= N; i++) {
			cout << i << " ";
		}
		cout << endl;
		return 0;
	}
	vector<int>dis(N, MOD);
	int root = 0;
	Calculate_Depth(edge, dis, root);
	vector<int>dnum(2);
	for (int i = 0; i < N; i++) {
		dnum[dis[i] & 1]++;
	}
	vector<int>ans(N);
	vector<vector<int>>box(3);
	vector<int>bag;
	for (int i = 1; i <= N; i += 3) {
		bag.push_back(i);
	}
	for (int i = 2; i <= N; i += 3) {
		bag.push_back(i);
	}
	for (int i = 3; i <= N; i += 3) {
		bag.push_back(i);
	}
	if (min(dnum[0], dnum[1]) < (N + 1) / 3) {
		if (dnum[0] < dnum[1]) {
			for (int i = 0; i < N; i++) {
				if (dis[i] & 1)continue;
				ans[i] = bag.back();
				bag.pop_back();
			}
			for (int i = 0; i < N; i++) {
				if (dis[i] & 1) {
					ans[i] = bag.back();
					bag.pop_back();
				}
			}
		}
		else {
			for (int i = 0; i < N; i++) {
				if (dis[i] & 1) {
					ans[i] = bag.back();
					bag.pop_back();
				}
			}
			for (int i = 0; i < N; i++) {
				if (dis[i] & 1) continue;
				ans[i] = bag.back();
				bag.pop_back();
			}
		}
		for (auto i : ans)cout << i << " ";
		cout << endl;
		return 0;
	}
	for (int i = 1; i <= N; i++) {
		box[i % 3].push_back(i);
	}
	if (dnum[0] > dnum[1]) {
		for (int i = 0; i < N; i++) {
			if (dis[i] & 1) {
				if (box[2].empty()) {
					ans[i] = box[0].back();
					box[0].pop_back();
				}
				else {
					ans[i] = box[2].back();
					box[2].pop_back();
				}
			}
			else {
				if (box[1].empty()) {
					ans[i] = box[0].back();
					box[0].pop_back();
				}
				else {
					ans[i] = box[1].back();
					box[1].pop_back();
				}
			}
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			if (dis[i] % 2 == 0) {
				if (box[2].empty()) {
					ans[i] = box[0].back();
					box[0].pop_back();
				}
				else {
					ans[i] = box[2].back();
					box[2].pop_back();
				}
			}
			else {
				if (box[1].empty()) {
					ans[i] = box[0].back();
					box[0].pop_back();
				}
				else {
					ans[i] = box[1].back();
					box[1].pop_back();
				}
			}
		}
	}
	for (auto i : ans)cout << i << " ";
	cout << endl;
}

Measured memory_bytes: 17136