#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(auto i=(a); i<(b); ++i)
#define REP(i,n) rep(i,0,n)
#define all(v) (v).begin(), (v).end()
#define rs resize
#define DBG(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl

const ld PI = acos(-1.0);
template<class T> using min_queue =
priority_queue<T, vector<T>, greater<T>>;
template<class T> int sz(const T &x) {
    return (int) x.size(); // copy the ampersand(&)!
}

template<class T> ostream& operator<<(ostream &os, vector<T> &v) {
    os << "\n[";
    for(T &x : v) os << x << ',';
    return os << "]\n";
}

struct pairhash {
    public:
    template<typename T1, typename T2>
    size_t operator()(const pair<T1, T2> &p) const {
        size_t lhs = hash<T1>()(p.x);
        size_t rhs = hash<T2>()(p.y);
        return lhs ^ (rhs+0x9e3779b9+(lhs<<6)+(lhs>>2));
    }
};

ll n;
vvi adj;
vvi ch;
//vvi A;
vi B;
//vector<vii> O;
vi C1;
vi C2;

void dfsInit(ll i, ll p, ll b) {
	for (ll j : adj[i]) {
		if (j != p) {
			ch[i].pb(j);
			dfsInit(j, i, (b+1)%2);
		}
	}
	B[i] = b;
	if (b == 0) {
		C1.pb(i);
	} else {
		C2.pb(i);
	}
}

/*void dfs2(ll i) {
	for (ll j : ch[i]) {
		dfs2(j);
	}
	for (ll j = 7; j >= 0; j++) {
		ll res = 100000000000;
		ii resO = {0, -1};
		for (ll k = 7; k > j; k++) {
			if ((k&j) == j && A[i][k] < res) {
				res = A[i][k];
				resO = O[i][k];
			}
		}
		ll r = 0;
		ll req = 0;
		if (j % 2 == 1) {
			r = 1;
		} else {
			req = 4;
		}
		if (j % 4 >= 2 || j % 8 >= 4) {
			req += (j>>1);
			for (ll c : ch[i]) {
				r += A[c][req];
			}
			if (r < res) {
				res = r;
				resO = {j, -1};
			}
		} else {
			for (ll c : ch[i]) {
				r += A[c][req + 3];
			}
			ll best = 10000000000;
			ll bestC = -1;
			for (ll c : ch[i]) {
				ll v = r - A[c][req+3] + A[c][req];
				if (v < best) {
					best = v;
					bestC = c;
				}
			}
			if (best < res) {
				res = best;
				resO = {j, bestC};
			}
		}
		A[i][j] = res;
		O[i][j] = resO;
	}
}*/



void run() {
	ll N;
	cin >> N;
	n = N;
	adj = vvi(N);
	ch = vvi(N);
	B = vi(N, 0);
	for (ll i = 0; i < N-1; i++) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfsInit(0, -1, 0);

	if (C1.size() > C2.size()) {
		swap(C1, C2);
	}
	vi R(N, 0);
	if (C1.size() <= N/3) {
		vi A1, A2;
		for (ll i = 1; i <= N; i++) {
			if (i%3 == 0 && A1.size() < C1.size()) {
				A1.pb(i);
			} else {
				A2.pb(i);
			}
		}
		for (ll i = 0; i < C1.size(); i++) {
			R[C1[i]] = A1[i];
		}
		for (ll i = 0; i < C2.size(); i++) {
			R[C2[i]] = A2[i];
		}
	} else {
		vi A1, A2;
		for (ll i = 0; 3*i+2 <= N; i++) {
			A1.pb(3*i+2);
		}
		for (ll i = 0; 3*i+1 <= N; i++) {
			A2.pb(3*i+1);
		}
		for (ll i = 1; 3*i <= N; i++) {
			if (A1.size() < C1.size()) {
				A1.pb(3*i);
			} else {
				A2.pb(3*i);
			}
		}
		for (ll i = 0; i < C1.size(); i++) {
			R[C1[i]] = A1[i];
		}
		for (ll i = 0; i < C2.size(); i++) {
			R[C2[i]] = A2[i];
		}
	}
	for (ll i = 0; i < N; i++) {
		cout << R[i] << " ";
	}
	cout << endl;
}

signed main() {
    // DON'T MIX "scanf" and "cin"!
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(20);
    run();
    return 0;
}


Measured memory_bytes: 34668