module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.container.rbtree;
import std.conv;
import std.stdio;
import std.string;
import std.traits;

struct Input
{
	int n;
	Edge[] edges;
}

struct Edge
{
    int n1;
    int n2;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
		n = readln().strip().to!int;
        edges.length = n - 1;
        foreach (i; 0..(n-1))
        {
            auto ar = readln().strip().split().map!(to!int).array();
            edges[i].n1 = ar[0];
            edges[i].n2 = ar[1];
        }
	}
}

class Node
{
    int i;
    int[] neighbors;
    int[] threes;
    this(int i) { this.i = i; }
}

auto main2(Input* input)
{
	with (input)
	{
        Node[] nodes;
        nodes.length = n + 1;
        foreach (int i, ref n; nodes)
            if (i != 0)
                n = new Node(i);

		foreach (e; edges)
        {
            nodes[e.n1].neighbors ~= e.n2;
            nodes[e.n2].neighbors ~= e.n1;
        }

        void search(int root, int current, int parent, int dist)
        {
            if (dist == 0)
            {
                nodes[root].threes ~= current;
                return;
            }

            foreach (n; nodes[current].neighbors)
            {
                if (n != parent)
                    search(root, n, current, dist - 1);
            }
        }

        foreach (i; 1..(n+1))
            search(i, i, -1, 3);

        auto sorted = nodes.dup;
        sorted[1..$].sort!"a.threes.length > b.threes.length"();

        int[] result;
        result.length = n + 1;

        int n3 = 3;
        int i = 1;
        while (i < n + 1)
        {
            auto node = sorted[i++];
            if (node.threes.length > 0)
            {
                if (n3 < n + 1)
                {
                    result[node.i] = n3;
                    foreach (n; node.threes)
                    {
                        nodes[n].threes.remove!(a => a == node.i);
                    }
                    n3 += 3;
                }
            }
        }

        int n12 = 1;
        foreach (ref r; result[1..$])
        {
            if (r != 0)
                continue;

            if (n3 < n + 1)
            {
                r = n3;
                n3 += 3;
            }
            else
            {
                r = n12;
                n12++;
                if (n12 % 3 == 0)
                    n12++;
            }
        }

        foreach (r; result[1..$])
        {
            writef("%d ", r);
        }
	}
}

alias retType = ReturnType!main2;

void printResult(T)(T result)
{
	static if (isFloatingPoint!T) writefln("%f", result);
	else writeln(result);
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	static if (is(retType == void))
		main2(&input);
	else
	{
		auto result = main2(&input);
		printResult(result);
	}
}
