use std::io::{Read, StdinLock};
use std::iter::{FromIterator, Iterator};
use std::str::{FromStr};
use std::string::String;
use std::collections::VecDeque;

//==============================================================================
//
// Input and formatting
//
//==============================================================================

fn read_bytes<T: FromIterator<char>>(s: &mut StdinLock) -> T {
    s.bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<T>()
}

fn reads(s: &mut StdinLock) -> String {
    read_bytes::<String>(s)
}

fn read<T: FromStr>(s: &mut StdinLock) -> T {
    reads(s).parse().ok().unwrap()
}

//==============================================================================
//
// Graph
//
//==============================================================================

type Vertex = usize;
type AdjacencyGraph = Vec<Vec<Vertex>>;

fn make_adjacency_graph<'a, I>(n: usize, edges: I) -> AdjacencyGraph
where
    I: Iterator<Item=&'a (Vertex, Vertex)>
{
    let mut g: Vec<Vec<Vertex>> = vec![vec![]; n];

    for &(u, v) in edges {
        g[u].push(v);
        g[v].push(u);
    }

    g.into_iter()
        .map(|mut adj| {
            adj.sort();
            adj.dedup();
            adj
        })
        .collect::<Vec<_>>()
}

//
// f: (vertex, parent, depth) -> ()
//
fn breadth_first<F>(g: &AdjacencyGraph, root: Vertex, mut f: F)
where
    F: FnMut(Vertex, Vertex, usize)
{
    let mut visited = vec![false; g.len()];
    let mut q0 = VecDeque::new();
    let mut q1 = VecDeque::new();

    visited[root] = true;
    q0.push_back(root);

    for d in 1.. {
        q1.clear();
        for &u in &q0 {
            for &v in &g[u] {
                if !visited[v] {
                    f(v, u, d);
                    visited[v] = true;
                    q1.push_back(v);
                }
            }
        }
        if q1.is_empty() {
            return;
        }
        std::mem::swap(&mut q0, &mut q1);
    }
}

//==============================================================================
//
// End of the common code
//
//==============================================================================

fn main() {
    let sin = std::io::stdin();
    let mut sin = sin.lock();

    let n = read::<usize>(&mut sin);
    let abs = (0 .. n - 1)
        .map(|_| (read::<usize>(&mut sin), read::<usize>(&mut sin)))
        .collect::<Vec<_>>();

    let g = make_adjacency_graph(n + 1, abs.iter());

    let mut grps = [vec![1], vec![]];
    breadth_first(&g, 1, |v, _, d| {
        grps[d % 2].push(v);
    });

    let mod3s = |m| (1 .. n + 1).filter(move |x| x % 3 == m);
    let gen =
        if grps[0].len() <= n / 3 {
            mod3s(0).chain(mod3s(1)).chain(mod3s(2))
        } else if grps[0].len() <  n - n / 3 {
            mod3s(1).chain(mod3s(0)).chain(mod3s(2))
        } else {
            mod3s(1).chain(mod3s(2)).chain(mod3s(0))
        };

    let mut p = vec![0; n + 1];
    for (i, &u) in gen.zip(grps[0].iter().chain(grps[1].iter())) {
        p[u] = i;
    }

    println!(
        "{}",
        p[1..].into_iter()
            .map(|i| i.to_string())
            .collect::<Vec<_>>()
            .join(" "));
}



Measured memory_bytes: 38208