#define _USE_MATH_DEFINES
#pragma region include

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////
vector< vector<int> > Edge,rEdge;
vector<int> visit;

void solve() {
	int N;
	cin >> N;
	Edge = vector<vector<int> >(N);
	rEdge = vector<vector<int> >(N);
	visit = vector<int>(N, -1);//-1未,0パリティ,1パリティ
	int a, b;
	//グラフの生成
	for (int i = 0; i < N - 1; ++i) {
		cin >> a >> b;
		a--; b--;
		Edge[a].push_back(b);
		Edge[b].push_back(a);
	}
	
	//パリティの設定
	queue<int> que;
	que.push(0);
	visit[0] = 0;
	while (!que.empty()) {
		int ter = que.front();
		que.pop();
		int size = Edge[ter].size();
		int nowP = visit[ter];
		int nextP = (nowP + 1) % 2;
		for (int k = 0; k < size; ++k) {
			int nextPoint = Edge[ter][k];
			if (visit[nextPoint] == -1) {
				que.push(nextPoint);
				visit[nextPoint] = nextP;
			}
		}
	}
	//////////////////////////////////////
	int A, B, C;//0,1,2==0あまり,1あまり,2あまり
	A = N / 3;
	B = N / 3;
	C = N / 3;
	if (N % 3 == 0) {
	}
	else if (N % 3 == 1) {
		B++;
	}
	else if (N % 3 == 2) {
		B++;
		C++;
	}

	vector<int> ans(N, -1);
	//パリティで多いほうに1余りを設定する。
	int BBB = 0;
	int CCC = 0;
	for (int i = 0; i < N; ++i) {
		if (visit[i] == 0) {
			BBB++;
		}
		else {
			CCC++;
		}
	}
	int terget = -1;
	if (BBB >= CCC) {
		terget = 0;
		if (CCC <= A) {
			terget = 3;
		}
	}
	else {
		terget = 1;
		if (BBB <= A) {
			terget = 4;
		}
	}

	vector<int> colorPos(3, 0);
	if (terget == 3) {
		//パリティ1に3の倍数を設定。
		for (int i = 0; i < N; ++i) {
			if (visit[i] == 1) {
				ans[i] = colorPos[0] * 3 + 3;
				colorPos[0]++;
			}
			else {
				if (colorPos[1] < B) {
					ans[i] = colorPos[1] * 3 + 1;
					colorPos[1]++;
				}
				else if(colorPos[2] < C) {
					ans[i] = colorPos[2] * 3 + 2;
					colorPos[2]++;
				}
				else {
					ans[i] = colorPos[0] * 3 + 3;
					colorPos[0]++;
				}
			}
		}
	}
	else if (terget == 4) {
		//パリティ0に3の倍数を設定。
		for (int i = 0; i < N; ++i) {
			if (visit[i] == 0) {
				ans[i] = colorPos[0] * 3 + 3;
				colorPos[0]++;
			}
			else {
				if (colorPos[1] < B) {
					ans[i] = colorPos[1] * 3 + 1;
					colorPos[1]++;
				}
				else if (colorPos[2] < C) {
					ans[i] = colorPos[2] * 3 + 2;
					colorPos[2]++;
				}
				else {
					ans[i] = colorPos[0] * 3 + 3;
					colorPos[0]++;
				}
			}
		}
	}
	else {
		for (int i = 0; i < N; ++i) {
			if (visit[i] == terget) {//1あまりを設定する。
				if (colorPos[1] < B) {//
					ans[i] = colorPos[1] * 3 + 1;
					colorPos[1]++;
				}
				else {
					ans[i] = colorPos[0] * 3 + 3;
					colorPos[0]++;
				}
			}
			else {//visit[i]!=terget
				if (colorPos[2] < C) {
					ans[i] = colorPos[2] * 3 + 2;
					colorPos[2]++;
				}
				else {
					ans[i] = colorPos[0] * 3 + 3;
					colorPos[0]++;
				}
			}
		}
	}
	//-------------------------------------------------
	for (int i = 0; i < N; ++i) {
		if (i)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

#pragma region main
signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()


Measured memory_bytes: 19952