Problem: We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

* For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.



Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

* 2\leq N\leq 2\times 10^5
* 1\leq a_i, b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}


Output

If no permutation satisfies the condition, print `-1`.

Otherwise, print a permutation satisfying the condition, with space in between. If there are multiple solutions, you can print any of them.

Example

Input

5
1 2
1 3
3 4
3 5


Output

1 2 5 4 3

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedOutputStream;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Queue;
import java.io.BufferedReader;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        LightWriter out = new LightWriter(outputStream);
        CThREE solver = new CThREE();
        solver.solve(1, in, out);
        out.close();
    }

    static class CThREE {
        public void solve(int testNumber, LightScanner in, LightWriter out) {
            int n = in.ints();
            int[] c = new int[3];
            for (int i = 1; i <= n; i++) c[i % 3]++;

            CThREE.Node[] nodes = new CThREE.Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new CThREE.Node();
            }
            for (int i = 1; i < n; i++) {
                int a = in.ints() - 1, b = in.ints() - 1;
                nodes[a].adj.add(nodes[b]);
                nodes[b].adj.add(nodes[a]);
            }
            nodes[0].dfs(null);
            Queue<CThREE.Node> p1 = new ArrayDeque<>(), p2 = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                if (nodes[i].depth % 2 == 0) p1.offer(nodes[i]);
                else p2.offer(nodes[i]);
            }


            if (p1.size() < p2.size()) {
                Queue<CThREE.Node> t = p1;
                p1 = p2;
                p2 = t;
            }
            //System.out.println(p1.size() + ", "+p2.size());

            if (p1.size() >= c[1] + c[2]) {
                for (int i = 1; i <= n; i++) {
                    if (i % 3 == 0) continue;
                    p1.poll().value = i;
                }
                for (int i = 3; i <= n; i += 3) {
                    if (p1.isEmpty()) p2.poll().value = i;
                    else p1.poll().value = i;
                }
            } else {
                for (int i = 1; i <= n; i += 3) p1.poll().value = i;
                for (int i = 2; i <= n; i += 3) p2.poll().value = i;
                for (int i = 3; i <= n; i += 3) {
                    if (p1.isEmpty()) p2.poll().value = i;
                    else p1.poll().value = i;
                }
            }
            for (int i = 0; i < n; i++) {
                out.ans(nodes[i].value);
            }
            out.ln();
        }

        static class Node {
            int depth = -1;
            int value;
            List<CThREE.Node> adj = new ArrayList<>();

            void dfs(CThREE.Node parent) {
                depth = parent == null ? 0 : parent.depth + 1;
                for (CThREE.Node n : adj) {
                    if (n == parent) continue;
                    n.dfs(this);
                }
            }

        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new OutputStreamWriter(new BufferedOutputStream(out), Charset.defaultCharset()));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ans(String s) {
            if (!breaked) {
                print(' ');
            }
            return print(s);
        }

        public LightWriter ans(int i) {
            return ans(Integer.toString(i));
        }

        public LightWriter ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }
}