#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
/*
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;*/
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
typedef long long ll;
typedef pair<ll, ll> Pa;

/*
template <std::int_fast64_t Modulus> class modint {
	using u64 = std::int_fast64_t;
public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept {
		return modint(*this) /= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
};
#pragma endregion

typedef modint<MOD> m;
m func[400001];
void funcinit(int N)
{
	func[0] = 1;
	for (int i = 1; i <= N; i++)
	{
		func[i] = func[i - 1] * i;
	}
}
m comb(m n, m r)
{
	if (n.a <= 0 || n.a < r.a)
	{
		return 0;
	}
	return func[n.a] / (func[r.a] * func[(n - r).a]);
}*/

vector<int> to[200001];
int a[200001];
bool visited[200001] = { false };
set<int> odd;
set<int> even;
int main() {
	cin >> N;
	rep(i, N - 1) {
		cin >> A >> B;
		to[A].push_back(B);
		to[B].push_back(A);
	}
	queue<int> que;
	que.push(1);
	a[1] = 0;
	while (!que.empty()) {
		int curr = que.front(); que.pop();
		rep(i, to[curr].size()) {
			if (!visited[to[curr][i]]) {
				que.push(to[curr][i]);
				a[to[curr][i]] = a[curr] + 1;
				visited[to[curr][i]] = true;
			}
		}
	}
	if (N == 2) {
		cout << "1 2";
		return 0;
	}
	rep(i, N) {
		if (a[i + 1] % 2 == 0) {
			even.insert(i + 1);
		}
		else {
			odd.insert(i + 1);
		}
	}
	if (even.size() <= N / 3) {
		int state = 0;
		int index = 0;
		for (auto x : even) {
			a[x] = index * 3 + 3;
			index++;
			if (index * 3 + 3 > N) {
				state++;
				index = 0;
			}
		}
		for (auto x : odd) {
			if (state == 0) {
				a[x] = index * 3 + 3;
			}
			else if (state == 1) {
				a[x] = index * 3 + 1;
			}
			else {
				a[x] = index * 3 + 2;
			}
			index++;
			if ((state == 0 && index * 3 + 3 > N) || (state == 1 && index * 3 + 1 > N)){
				state++;
				index = 0;
			}
		}
	}
	else if (odd.size() <= N / 3) {
		int state = 0;
		int index = 0;
		for (auto x : odd) {
			a[x] = index * 3 + 3;
			index++;
			if (index * 3 + 3 > N) {
				state++;
				index = 0;
			}
		}
		for (auto x : even) {
			if (state == 0) {
				a[x] = index * 3 + 3;
			}
			else if (state == 1) {
				a[x] = index * 3 + 1;
			}
			else {
				a[x] = index * 3 + 2;
			}
			index++;
			if ((state == 0 && index * 3 + 3 > N) || (state == 1 && index * 3 + 1 > N)){
				state++;
				index = 0;
			}
		}
	}
	else {
		int state = 0;
		int index = 0;
		for (auto x : odd) {
			if (state == 0) a[x] = index * 3 + 1;
			else a[x] = index * 3 + 3;
			index++;
			if (state == 0 && index * 3 + 1 > N) {
				state++;
				index = 0;
			}
		}
		for (auto x : even) {
			if (state == 1) {
				a[x] = index * 3 + 3;
			}
			else {
				a[x] = index * 3 + 2;
			}
			index++;
			if (state == 1 && index * 3 + 3 > N) {
				state++;
				index = 0;
			}
		}
	}
	rep(i, N) {
		cout << a[i + 1] << " ";
	}
}


Measured memory_bytes: 23412