import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); } bool DEBUG = 0; 
void log(A ...)(lazy A a){ if(DEBUG) print(a); }
void print(){ writeln(""); } void print(T)(T t){ writeln(t); } void print(T, A ...)(T t, A a){ write(t, " "), print(a); }
string unsplit(T)(T xs){ return xs.array.to!(string[]).join(" "); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; } T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
T lowerTo(T)(ref T x, T y){ if(x > y) x = y; return x; } T raiseTo(T)(ref T x, T y){ if(x < y) x = y; return x; }

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
    int n = scan!int;
    Node[] nodes;
    foreach(i; 0 .. n) nodes ~= new Node(i);
    foreach(_; 0 .. n - 1){

        Node a = nodes[scan!int - 1], b = nodes[scan!int - 1];
        a.connectTo(b);
    }
    Node.root = nodes[0];

    int cnt1, cnt2;
    foreach(nd; nodes){
        if(nd.depth % 2) cnt1 += 1;
        else cnt2 += 1;
    }
    //log("cnt1:", cnt1, "cnt2:", cnt2);

    int[] ans = new int[](n);
    int[] isUsed = new int[](n + 1);
    if(cnt1 <= n / 3){ // depth 1 -> 3, depth 2 -> any
        int z = 3;
        foreach(nd; nodes) if(nd.depth % 2){
            ans[nd.id] = z, isUsed[z] = 1, z += 3;
        }
        z = 1;
        foreach(nd; nodes){
            if(ans[nd.id]) continue;
            while(isUsed[z]) z += 1;
            ans[nd.id] = z, isUsed[z] = 1;
        }
    }
    else if(cnt2 <= n / 3){ // depth 2 -> 3, depth 1 -> any
        int z = 3;
        foreach(nd; nodes) if(nd.depth % 2 == 0){
            ans[nd.id] = z, isUsed[z] = 1, z += 3;
        }
        z = 1;
        foreach(nd; nodes){
            if(ans[nd.id]) continue;
            while(isUsed[z]) z += 1;
            ans[nd.id] = z, isUsed[z] = 1;
        }
    }
    else{ // depth 1 -> 1, depth 2 -> 2
        int x = 1, y = 2, z = 3;
        foreach(nd; nodes){
            //log("nd:", nd.id + 1, "x:", x, "y:", y, "z:", z, "ans:", ans);
            if(nd.depth % 2){
                if(x <= n) ans[nd.id] = x, isUsed[x] = 1, x += 3;
                else ans[nd.id] = z, isUsed[z] = 1, z += 3;
            }
            else{
                if(y <= n) ans[nd.id] = y, isUsed[y] = 1, y += 3;
                else ans[nd.id] = z, isUsed[z] = 1, z += 3;
            }
        }
    }

    ans.unsplit.print;

}

// 最小共通祖先, lca, 最低共通祖先, Lowest Common Ancestor, Least Common Ancestor
// パスの長さ, 木上の距離, ツリー上の距離, ツリーでの最短経路の長さ
// ※ループがある場合や、森になっている場合は非対応
// 使い方は後のテストコードを参照

class Node{
	static Node[] all; // 存在する全てのノード
	int id;
	Node[] nodes; // 隣接ノード（親も子も含む）
	int depth; // 根は 0
	Node[] parents; // 1代前、2代前、4代前、8代前、…… の親（いない場合は打切り）
	private bool isDone;

	// 頂点を作成（根付き木は壊れる）
	this(int id){
		this.id = id;
		all ~= this;
		_root = null;
	}

	// 辺を作成（根付き木は壊れる）
	void connectTo(Node nd){
		this.nodes ~= nd, nd.nodes ~= this;
		_root = null;
	}

	// 根付き木にする（木になってない場合は未定義）
	private static Node _root;
	static Node root(){ return _root; }
	static Node root(Node r){

		// parents[0] を設定する
		foreach(nd; all) nd.isDone = 0;
		r.parents = [], r.depth = 0;
		Node[] ndq = [r];
		for(int i = 0; i < ndq.length; i ++){
			Node p = ndq[i];
			p.isDone = 1;
			foreach(q; p.nodes) if(! q.isDone){
				q.parents = [p], q.depth = p.depth + 1;
				ndq ~= q;
			}
		}

		// parents[1] 以降を設定する（30 はマジックナンバー、log(2;N) 程度）
		foreach(i; 1 .. 30) foreach(nd; all){
			if(i <= nd.parents.length){
				Node par = nd.parents[i - 1];
				if(i <= par.parents.length) nd.parents ~= par.parents[i - 1];
			}
		}

		return _root = r;
	}
	
	// 2点間の距離
	int distTo(Node nd){
		Node p = this.lca(nd);
		return (this.depth - p.depth) + (nd.depth - p.depth);
	}

	// 最小共通祖先
	Node lca(Node nd){
		assert(root);
		if(this.depth > nd.depth) return nd.lca(this);
		if(this.depth < nd.depth) foreach_reverse(p; nd.parents) if(p.depth >= this.depth) return lca(p);
		foreach_reverse(i, p; nd.parents) if(this.parents[i].id != p.id){
			return this.parents[i].lca(p);
		}
		if(this.id == nd.id) return this; else return this.parents[0];
	}
}



Measured memory_bytes: 103420