#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define nmax_def 220000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

class Graph_class {
public:
	bool graph_from1 = true;
	bool graph_tree = true;
	bool graph_weight = false;
	bool graph_digraph = false;
	int Vnum;
	int Enum;
	vector<pii> edgelist;
	vl edgeweight;
	vector<vi> adjlist;
	vector<vl> adjlistweight;
	vi adjnum;

	vi adj_to_root;
	vector<int> DP;
	vi vlist_from_root;
	vl xdist;

	vb x_visited;
	deque<int> x_que;

	void read_edge();
	void read_edge_array();
	void adjini();
	void visited_ini();
	void graph_BFS(ll BFS_ini);
	void graph_DFS(ll DFS_ini);
	void Dijkstra(int x);
	bool Bellman_Ford(int x);
	ll diameter();
	void ReRooting(ll root);
	Graph_class Kruskal();
	int dim_num(int dim);
	void solve();

	bool xydist_def = false;
};

// ----- UnionFind -----

class UnionFind {
public:
	vi par;
	vi adjnum;
	int N;

	void UnionFind_ini(int Narg);
	int root(int x);
	void unite(int x, int y);
	bool same(int x, int y);
	int adjnum_func(int x);
};

void UnionFind::UnionFind_ini(int Narg) {
	N = Narg;
	adjnum.resize(N);
	par.resize(N);
	rep(i, N) {
		adjnum[i] = 1;
		par[i] = i;
	}
}

int UnionFind::root(int x) {
	if (par[x] == x)
		return x;
	par[x] = root(par[x]);
	return par[x];
}

void UnionFind::unite(int x, int y) {
	int rx = root(x);
	int ry = root(y);
	if (rx == ry)
		return;
	par[rx] = ry;
	adjnum[ry] += adjnum[rx];
	return;
}

bool UnionFind::same(int x, int y) {
	int rx = root(x);
	int ry = root(y);
	return rx == ry;
}

int UnionFind::adjnum_func(int x) {
	int rx = root(x);
	return adjnum[rx];
}

// ----- graph -----

void Graph_class::read_edge() {
	cin >> Vnum;
	if (graph_tree)
		Enum = Vnum - 1;// graph
	else
		cin >> Enum;
	edgelist.resize(Enum);
	edgeweight.resize(Enum, 1);
	rep(i, Enum) {
		if (graph_weight)
			cin >> edgelist[i].first >> edgelist[i].second >> edgeweight[i];
		else
			cin >> edgelist[i].first >> edgelist[i].second;
		if (graph_from1) {
			edgelist[i].first--;
			edgelist[i].second--;
		}
	}
	return;
}

void Graph_class::read_edge_array() {
	cin >> Vnum;
	Enum = 0;
	rep(i, Vnum) {
		string S;
		cin >> S;
		rep(j, Vnum) {
			if (S[j] == '1') {
				if (graph_digraph || i < j) {
					pii edgetmp = make_pair(i, j);
					edgelist.push_back(edgetmp);
					Enum++;
				}
			}
		}
	}
	if (!graph_digraph)
		Enum /= 2;
	return;
}

void Graph_class::adjini() {
	adjnum.resize(Vnum);
	xdist.resize(Vnum, -1);
	adjlist.resize(Vnum);
	if (graph_weight)
		adjlistweight.resize(Vnum);
	adj_to_root.resize(Vnum, -1);
	DP.resize(Vnum, 0);
	rep(i, Vnum)
		adjnum[i] = 0;
	rep(i, Enum) {
		int x = edgelist[i].first;
		int y = edgelist[i].second;
		adjlist[x].push_back(y);
		if (!graph_digraph)
			adjlist[y].push_back(x);
		if (graph_weight) {
			ll xyweight = edgeweight[i];
			adjlistweight[x].push_back(xyweight);
			if (!graph_digraph)
				adjlistweight[y].push_back(xyweight);
		}
		adjnum[x]++;
		if (!graph_digraph)
			adjnum[y]++;
	}
	x_visited.resize(Vnum);
	visited_ini();

	return;
}

void Graph_class::visited_ini() {
	rep(i, Vnum) {
		x_visited[i] = false;
		adj_to_root[i] = -1;
	}
	x_que.clear();
}

void Graph_class::graph_BFS(ll BFS_ini) {
	visited_ini();
	x_que.push_back(BFS_ini);
	x_visited[BFS_ini] = true;

	// option
	xdist[BFS_ini] = 0;
	vlist_from_root.clear();
	vlist_from_root.push_back(BFS_ini);
	//cout << BFS_ini << endl;

	while (!x_que.empty()) {
		int x = x_que.front();
		x_que.pop_front();
		rep(i, adjnum[x]) {
			int x_new = adjlist[x][i];
			int dist_new = 1;
			if (graph_weight)
				dist_new = adjlistweight[x][i];
			if (!x_visited[x_new]) {
				x_visited[x_new] = true;
				x_que.push_back(x_new);

				// option
				adj_to_root[x_new] = x;
				vlist_from_root.push_back(x_new);
				xdist[x_new] = xdist[x] + dist_new;
				//cout << x_new << endl;
			}
		}
	}
	return;
}

void Graph_class::graph_DFS(ll DFS_ini) {
	visited_ini();
	x_que.push_back(DFS_ini);
	x_visited[DFS_ini] = true;

	while (!x_que.empty()) {
		int x = x_que.back();
		x_que.pop_back();

		// option
		//cout << x << endl;

		rep(i, adjnum[x]) {
			int x_new = adjlist[x][i];
			if (!x_visited[x_new]) {
				x_visited[x_new] = true;
				x_que.push_back(x_new);
			}
		}
	}
	return;
}

void Graph_class::Dijkstra(int x) {
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > xdist_que;
	ll max_tmp = pow(10, 18) * 4;
	rep(i, Vnum)
		xdist[i] = max_tmp;
	xdist[x] = 0;
	pair<ll, int> xdist_que_tmp;
	xdist_que_tmp.first = 0;
	xdist_que_tmp.second = x;
	xdist_que.push(xdist_que_tmp);
	while (!xdist_que.empty()) {
		xdist_que_tmp = xdist_que.top();
		xdist_que.pop();
		ll xdist_tmp = xdist_que_tmp.first;
		int x_tmp = xdist_que_tmp.second;
		if (xdist[x_tmp] == xdist_tmp) {
			rep(i, adjnum[x_tmp]) {
				int x_new = adjlist[x_tmp][i];
				ll dist_diff;
				if (graph_weight)
					dist_diff = adjlistweight[x_tmp][i];
				else dist_diff = 1;
				if (xdist[x_new] > xdist[x_tmp] + dist_diff) {
					xdist[x_new] = xdist[x_tmp] + dist_diff;
					xdist_que_tmp.first = xdist[x_new];
					xdist_que_tmp.second = x_new;
					xdist_que.push(xdist_que_tmp);
				}
			}
		}
	}
	return;
}

bool Graph_class::Bellman_Ford(int x) {
	ll max_tmp = pow(10, 18) * 4;
	rep(i, Vnum)
		xdist[i] = max_tmp;
	xdist[x] = 0;
	rep(xtmp, Vnum) {
		rep(etmp, Enum) {
			ll weighttmp = edgeweight[etmp];
			int x_from = edgelist[etmp].first;
			int x_to = edgelist[etmp].second;
			if (xdist[x_to] > xdist[x_from] + weighttmp) {
				xdist[x_to] = xdist[x_from] + weighttmp;
				if (xtmp == Vnum - 1)
					return true;
			}
		}
	}
	return false;
}

ll Graph_class::diameter() {
	ll anstmp = 0;
	if (graph_tree) {
		ll anstmp_i = 0;
		pii longest;
		graph_BFS(0);
		rep(i, Vnum) {
			if (xdist[i] > anstmp) {
				anstmp = xdist[i];
				anstmp_i = i;
			}
		}
		longest.first = anstmp_i;
		anstmp = 0, anstmp_i = 0;
		graph_BFS(longest.first);
		rep(i, Vnum) {
			if (xdist[i] > anstmp) {
				anstmp = xdist[i];
				anstmp_i = i;
			}
		}
		longest.second = anstmp_i;
	}
	else {
		rep(i, Vnum) {
			Dijkstra(i);
			rep(j, Vnum) {
				anstmp = max(anstmp, xdist[j]);
			}
		}
	}
	return anstmp;
}


void Graph_class::ReRooting(ll root) {
	rep(i, Vnum) {
		DP[i] = 1;
	}
	graph_BFS(root);
	rrep(i, Vnum) { // 根から遠い点から見る
		ll x = vlist_from_root[i];
		rep(j, adjnum[x]) {
			ll x_new = adjlist[x][j];
			if (x_new == adj_to_root[x]) // 根側
				continue;
			DP[x] += DP[x_new];
		}
	}
	return;
}

Graph_class Graph_class::Kruskal() {
	assert(!graph_digraph);
	Graph_class tree;
	vector<pair<ll, pii> > edgeweight_sort(Enum);
	rep(i, Enum) {
		edgeweight_sort[i].first = edgeweight[i];
		edgeweight_sort[i].second = edgelist[i];
	}
	sort(edgeweight_sort.begin(), edgeweight_sort.end(), less<pair<ll, pii> >());
	UnionFind tree_uf;
	tree_uf.UnionFind_ini(Vnum);
	tree.Vnum = Vnum;
	tree.Enum = 0;
	rep(i, Enum) {
		ll edgeweighttmp = edgeweight_sort[i].first;
		pii edgetmp = edgeweight_sort[i].second;
		if (!tree_uf.same(edgetmp.first, edgetmp.second)) {
			tree_uf.unite(edgetmp.first, edgetmp.second);
			tree.edgelist.push_back(edgetmp);
			tree.edgeweight.push_back(edgeweighttmp);
			tree.Enum++;
		}
	}
	ll ans = 0;
	rep(i, tree.Enum) {
		ans += tree.edgeweight[i];
		cout << (tree.edgelist[i].first + 1) << " " << (tree.edgelist[i].second + 1) << " " << tree.edgeweight[i] << endl;
	}
	cout << ans << endl;

	tree.graph_from1 = true;
	tree.graph_tree = true;
	tree.graph_weight = true;
	tree.graph_digraph = false;

	tree.adjini();
	return tree;
}


int Graph_class::dim_num(int dim) {
	int anstmp = 0;
	rep(i, Vnum) {
		if (adjnum[i] == dim)
			anstmp++;
	}
	return anstmp;
}

void Graph_class::solve() {
	graph_BFS(0);
	vi ans(Vnum);
	vi count(3, 0);
	vi anscount(3, 0);
	anscount[0]++;
	vi anslist(Vnum);
	rep(i, Vnum) {
		anslist[i] = xdist[i] % 2 + 1;
		count[anslist[i]]++;
	}
	if (count[1] * 2 < count[2]) {
		rep(i, Vnum) {
			switch (anslist[i])
			{
			case 1:
				ans[i] = anscount[0] * 3;
				anscount[0]++;
				break;
			case 2:
				ans[i] = 1 + anscount[1] * 3;
				anscount[1]++;
				if(ans[i]>Vnum){
					ans[i] = 2 + anscount[2] * 3;
					anscount[2]++;
					if (ans[i] > Vnum) {
						ans[i] = anscount[0] * 3;
						anscount[0]++;
					}
				}
				break;
			}
		}
	}
	else if (count[2] * 2 < count[1]) {
		rep(i, Vnum) {
			switch (anslist[i])
			{
			case 2:
				ans[i] = anscount[0] * 3;
				anscount[0]++;
				break;
			case 1:
				ans[i] = 1 + anscount[1] * 3;
				anscount[1]++;
				if (ans[i] > Vnum) {
					ans[i] = 2 + anscount[2] * 3;
					anscount[2]++;
					if (ans[i] > Vnum) {
						ans[i] = anscount[0] * 3;
						anscount[0]++;
					}
				}
				break;
			}
		}
	}
	else {
		rep(i, Vnum) {
			switch (anslist[i])
			{
			case 1:
				ans[i] = 1 + anscount[1] * 3;
				anscount[1]++;
				if (ans[i] > Vnum) {
					ans[i] = anscount[0] * 3;
					anscount[0]++;
				}
				break;
			case 2:
				ans[i] = 2 + anscount[2] * 3;
				anscount[2]++;
				if (ans[i] > Vnum) {
					ans[i] = anscount[0] * 3;
					anscount[0]++;
				}
				break;
			}
		}
	}
	rep(i, Vnum)
		cout << ans[i] << " ";
	cout << endl;
	return;
}

int main(void) {
	Graph_class graph;
	graph.read_edge();
	graph.adjini();
	graph.solve();
	return 0;
}

Measured memory_bytes: 24820