#ifndef __GRAPH_H__
#define __GRAPH_H__

/* updated: 2020-02-11 */

#include <vector>
#include <cstdint>
#include <iostream>
#include <string>
#include <sstream>

struct GraphEdge {
	int from = 0;
	int to = 0;

	GraphEdge() = default;
	GraphEdge(int from, int to);
};

/* 有向グラフクラス(特に無向グラフクラスは用意せず、両方向に辺を張ることで対応する) */
class Graph {
public:
	using EdgeID = int;
	using Edge = GraphEdge;
	using List = std::vector<EdgeID>;

private:
	std::vector<List> ids_m;
 	std::vector<Edge> edges_m;

public:
	Graph() = default;
	Graph(Graph&&) = default;
	Graph(const Graph&) = default;
	Graph& operator=(Graph&&) = default;
	Graph& operator=(const Graph&) = default;

	explicit Graph(int size);
	int size() const;
	int edgeCount() const;
	void init(int new_size);
	void reserve(int edge_count);
	
	void add(int from, int to, bool directed = true);
	const List& row(int from) const;
	const Edge& getEdge(EdgeID id) const;
	const std::vector<Edge>& getEdges() const;
	EdgeID reverseEdgeOf(EdgeID id) const;

	std::string toString() const;
	void debug() const;
};

Graph inputGraph(int size, int edge_count, bool directed = true, bool one_based = true, std::istream& ist = std::cin);
// outputGraph

template <class T>
class WeightedGraph {
	Graph graph_m;
	std::vector<T> weights_m;

public:
	WeightedGraph() = default;
	WeightedGraph(WeightedGraph&&) = default;
	WeightedGraph(const WeightedGraph&) = default;
	WeightedGraph& operator=(WeightedGraph&&) = default;
	WeightedGraph& operator=(const WeightedGraph&) = default;

	explicit WeightedGraph(int size);
	void init(int new_size);
	void add(int from, int to, T&& weight, bool directed = true);
	void add(int from, int to, const T& weight, bool directed = true);

	const Graph& getGraph() const;
	const std::vector<T>& getWeights() const;

	std::string toString() const;
	void debug() const;
};

template<class T>
inline WeightedGraph<T>::WeightedGraph(int size) 
	: graph_m(size) {
}

template<class T>
inline void WeightedGraph<T>::init(int new_size) {
	graph_m.init(new_size);
}

template<class T>
inline void WeightedGraph<T>::add(int from, int to, T&& weight, bool directed) {
	if (!directed) {
		add(from, to, std::move(weight), true);
		add(to, from, std::move(weight), true);
		return;
	}

	graph_m.add(from, to);
	weights_m.push_back(std::move(weight));
}

template<class T>
inline void WeightedGraph<T>::add(int from, int to, const T& weight, bool directed) {
	if (!directed) {
		add(from, to, weight, true);
		add(to, from, weight, true);
		return;
	}

	graph_m.add(from, to);
	weights_m.push_back(weight);
}

template<class T>
inline const Graph& WeightedGraph<T>::getGraph() const {
	return graph_m;
}

template<class T>
inline const std::vector<T>& WeightedGraph<T>::getWeights() const {
	return weights_m;
}

template<class T>
inline std::string WeightedGraph<T>::toString() const {
	std::ostringstream stream;
	for (int from = 0; from < graph_m.size(); ++from) {
		stream << from << ": [";
		for (auto id : graph_m.row(from)) {
			const auto& edge = graph_m.getEdge(id);
			int to = edge.to;
			stream << ' ' << to << '(' << weights_m[id] << ')';
		}
		stream << " ]" << std::endl;
	}
	return stream.str();
}

template<class T>
inline void WeightedGraph<T>::debug() const {
	std::cerr << toString() << std::endl;
}

template <class T>
WeightedGraph<T> inputWeightedGraph(int size, int edge_count, bool directed = true, bool one_based = true, std::istream& ist = std::cin);

template <class T>
WeightedGraph<T> inputWeightedGraph(int size, int edge_count, bool directed, bool one_based, std::istream& ist) {
	WeightedGraph<T> ret(size);
	for (int j = 0; j < edge_count; ++j) {
		int a, b;
		T weight;
		ist >> a >> b >> weight;
		if (one_based) {
			--a; --b;
		}

		if (directed) {
			ret.add(a, b, weight);
		} else {
			ret.add(a, b, weight);
			ret.add(b, a, weight);
		}
	}
	return ret;
}

#endif
#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <cassert>
#include <sstream>

GraphEdge::GraphEdge(int from, int to)
	: from(from), to(to) {
}

Graph::Graph(int size) 
	: ids_m(size) {
}

int Graph::size() const {
	return ids_m.size();
}

int Graph::edgeCount() const {
	return edges_m.size();
}

void Graph::init(int new_size) {
	assert(new_size >= size());
	ids_m.resize(new_size);
}

void Graph::reserve(int edge_count) {
	edges_m.reserve(edge_count);
}

void Graph::add(int from, int to, bool directed) {
	if (!directed) {
		add(from, to, true);
		add(to, from, true);
		return;
	}

	ids_m[from].push_back(edges_m.size());
	edges_m.push_back(Edge(from, to));
}

const Graph::List& Graph::row(int from) const {
	assert(from >= 0 && from < size());
	return ids_m[from];
}

const Graph::Edge& Graph::getEdge(EdgeID id) const {
	assert(id >= 0 && id < edgeCount());
	return edges_m[id];
}

const std::vector<Graph::Edge>& Graph::getEdges() const {
	return edges_m;
}

/* 無向グラフ用: 逆辺を参照する */
Graph::EdgeID Graph::reverseEdgeOf(EdgeID id) const {
	return id ^ 0x1;
}

std::string Graph::toString() const {
	std::ostringstream stream;
	for (int from = 0; from < size(); ++from) {
		stream << from << ": [";
		for (auto id : row(from)) {
			const auto& edge = getEdge(id);
			int to = edge.to;
			stream << ' ' << to;
		}
		stream << " ]" << std::endl;
	}
	return stream.str();
}

void Graph::debug() const {
	std::cerr << toString() << std::endl;
}

Graph inputGraph(int size, int edge_count, bool directed, bool one_based, std::istream& ist) {
	Graph ret(size);
	for (int j = 0; j < edge_count; ++j) {
		int a, b;
		ist >> a >> b;
		if (one_based) {
			--a; --b;
		}

		if (directed) {
			ret.add(a, b);
		} else {
			ret.add(a, b);
			ret.add(b, a);
		}
	}
	return ret;
}
#ifndef __GRAPH_UTIL_H__
#define __GRAPH_UTIL_H__

/* updated: 2019-12-22 */

// required: Graph

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

Graph createReverseGraph(const Graph& graph);
Graph createComplementGraph(const Graph& graph);

bool isBipartite(const Graph& graph);
std::vector<bool> colorBipartiteGraph(const Graph& graph);
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring);

std::vector<std::vector<int>> connectedComponents(const Graph& graph);

#endif

#ifdef ONLY_MY_ENVIR
#include "GraphUtil.h"
#endif

#include <cassert>
#include <stack>


/* 辺の向きを逆転させたグラフを作成 O(n + m) */
Graph createReverseGraph(const Graph& graph) {
	const int size = graph.size();
	Graph ret(size);
	ret.reserve(graph.edgeCount());

	for (const auto& edge : graph.getEdges()) {
		ret.add(edge.to, edge.from);
	}
	return ret;
}

/* TODO: 無向グラフは？ */
/* 補グラフを作成 O(n^2 + m) */
Graph createComplementGraph(const Graph& graph) {
	const int size = graph.size();
	std::vector<std::vector<bool>> matrix(size, std::vector<bool>(size, true));
	for (int i = 0; i < size; ++i) {
		matrix[i][i] = false;
	}

	for (const auto& edge : graph.getEdges()) {
		matrix[edge.to][edge.from] = false;
	}

	Graph ret(size);
	for (int i = 0; i < size; ++i) {
		for (int j = 0; j < size; ++j) {
			if (matrix[i][j]) {
				ret.add(i, j);
			}
		}
	}
	return ret;
}

/* 無向グラフの二部グラフ判定 O(n + m) */
bool isBipartite(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	return isBipartiteSub(graph, coloring);
}

/* 二部グラフとなるような頂点の分割を一つ見つける O(n + m) */
/* out: 頂点 -> 組 { 0, 1 } */
std::vector<bool> colorBipartiteGraph(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	bool succeeded = isBipartiteSub(graph, coloring);
	assert(succeeded);
	return coloring;
}

/* out: (bool, coloring) = (二部グラフかどうか, 二部グラフのときの塗り分け) */
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring) {
	assert(graph.size() == coloring.size());

	struct State {
		int vertex;
		bool color;
		State(int vertex, bool color)
			: vertex(vertex), color(color) {
		}
	};

	const int size = graph.size();
	std::vector<bool> visited(size);
	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::stack<State> stack;
		stack.push(State(from, false));
		while (!stack.empty()) {
			const State state = stack.top();
			stack.pop();

			int from = state.vertex;
			bool color = state.color;
			if (visited[from]) {
				if (coloring[from] != color) return false;
				continue;
			}

			visited[from] = true;
			coloring[from] = color;

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(State(to, !color));
			}
		}
	}
	return true;
}

/* 連結成分分解 O(n + m) */
/* out: [各連結成分の頂点リスト] のリスト */
std::vector<std::vector<int>> connectedComponents(const Graph& graph) {
	std::vector<std::vector<int>> groups;

	const int size = graph.size();
	std::vector<bool> visited(size);
	
	auto search = [&graph, &visited](int start, std::vector<int>& group) -> void {
		std::stack<int> stack;
		stack.push(start);
		while (!stack.empty()) {
			int from = stack.top();
			stack.pop();

			if (visited[from]) continue;
			visited[from] = true;
			group.push_back(from);

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(to);
			}
		}
	};

	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::vector<int> group;
		search(from, group);
		groups.push_back(std::move(group));
	}

	return groups;
}
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using uint = uint32_t;
using LL = int64_t;
using ULL = uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Accumulator.h"
#include "Algebraic.h"
#include "BinaryMatrix.h"
#include "BinaryTree.h"
#include "Bipartite.h"
#include "BIT.h"
#include "Compressor.h"
#include "Decompositions.h"
#include "DynamicMod.h"
#include "Factorization.h"
#include "FFT.h"
#include "FlowSolver.h"
#include "Graph.h"
#include "GraphUtil.h"
#include "LazySegmentTree.h"
#include "LIS.h"
#include "Math.h"
#include "MathUtil.h"
#include "Matrix.h"
#include "MinCostFlowSolver.h"
#include "MinMax.h"
#include "Numbers.h"
#include "Optimize.h"
#include "Permutation.h"
#include "Polynomial.h"
#include "Position.h"
#include "Range.h"
#include "Rational.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "Sets.h"
#include "Shortest.h"
#include "SlidingWindow.h"
#include "SpanningTree.h"
#include "StringSearching.h"
#include "SuffixArray.h"
#include "Tree.h"
#include "UnionFind.h"
#include "VectorUtil.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>>(istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<<(ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif


int main() {
	int N;
	cin >> N;
	Graph g = inputGraph(N, N - 1, false);
	auto colors = colorBipartiteGraph(g);
	
	int cnt = count(colors.begin(), colors.end(), false);
	int rem = count(colors.begin(), colors.end(), true);
	if (cnt > rem) {
		swap(cnt, rem);
		REP(i, 0, N) {
			colors[i] = !colors[i];
		}
	}

	vector<int> ans(N);
	if (3 * cnt <= N) {
		set<int> zero;
		set<int> nonzero;
		REP(i, 1, N + 1) {
			(i % 3 == 0 ? zero : nonzero).insert(i);
		}
		REP(i, 0, N) {
			if (colors[i] == false) {
				ans[i] = *zero.begin();
				zero.erase(zero.begin());
			} else {
				if (nonzero.empty()) {
					ans[i] = *zero.begin();
					zero.erase(zero.begin());
				} else {
					ans[i] = *nonzero.begin();
					nonzero.erase(nonzero.begin());
				}
			}
		}
	} else {
		set<int> zero;
		set<int> one;
		set<int> two;
		REP(i, 1, N + 1) {
			(i % 3 == 0 ? zero : i % 3 == 1 ? one : two).insert(i);
		}
		REP(i, 0, N) {
			if (colors[i] == false) {
				if (one.empty()) {
					ans[i] = *zero.begin();
					zero.erase(zero.begin());
				} else {
					ans[i] = *one.begin();
					one.erase(one.begin());
				}
			} else {
				if (two.empty()) {
					ans[i] = *zero.begin();
					zero.erase(zero.begin());
				} else {
					ans[i] = *two.begin();
					two.erase(two.begin());
				}
			}
		}
	}
	
	REP(i, 0, N) {
		cout << ans[i] << ' ';
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 26988