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.util.*;
import java.io.*;

public class Main {
    public static InputReader in;
    public static PrintWriter out;
    static int[][] G;
    static int[] color;
    public static void main(String[] args) {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);
        int n = in.nextInt();
        int[] a = new int[n - 1];
        int[] b = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            a[i] = u;
            b[i] = v;
        }
        G = buildGraph(n, a, b);
        color = new int[n];
        dfs(0, -1, 0);
        int sum1 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += color[i];
        }
        int sum0 = n - sum1;
        if (sum0 > sum1) {
            int tmp = sum0;
            sum0 = sum1;
            sum1 = tmp;
            for (int i = 0; i < n; i++) {
                color[i] ^= 1;
            }
        }
        int numOfMultiple3 = n / 3;
        int[] p = new int[n];
        if (numOfMultiple3 >= sum0) {
            HashMap<Integer, Boolean> map = new HashMap<>();
            int ptr = 3;
            for (int i = 0; i < n; i++) {
                if (color[i] == 0) {
                    p[i] = ptr;
                    map.put(ptr, true);
                    ptr += 3;
                }
            }
            ptr = 1;
            for (int i = 0; i < n; i++) {
                if (p[i] == 0) {
                    p[i] = ptr++;
                    while (map.get(ptr) != null) ptr++;
                }
            }
        }  else {
            int ptr = 1;
            for (int i = 0; i < n; i++) {
                if (color[i] == 1) {
                    p[i] = ptr;
                    ptr += 3;
                    if (ptr > n) break;
                }
            }
            ptr = 2;
            for (int i = 0; i < n; i++) {
                if (color[i] == 0) {
                    p[i] = ptr;
                    ptr += 3;
                    if (ptr > n) break;
                }
            }
            ptr = 3;
            for (int i = 0; i < n; i++) {
                if (p[i] == 0) {
                    p[i] = ptr;
                    ptr += 3;
                }
            }
        }
        for (int x : p) {
            out.print(x + " ");
        }
        out.println();
        out.close();
    }
    static void dfs(int u, int f, int c) {
        color[u] = c;
        for (int v : G[u]) {
            if (v == f) continue;
            dfs(v, u, c ^ 1);
        }
    }
    static int[][] buildGraph(int n, int[] a, int[] b) {
        int[] cnt = new int[n];
        for (int x : a) {
            cnt[x] += 1;
        }
        for (int x : b) {
            cnt[x] += 1;
        }
        int[][] G = new int[n][];
        for (int i = 0; i < n; i++) {
            G[i] = new int[cnt[i]];
        }
        for (int i = 0; i < n - 1; i++) {
            G[a[i]][--cnt[a[i]]] = b[i];
            G[b[i]][--cnt[b[i]]] = a[i];
        }
        return G;
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public Long nextLong() {
            return Long.parseLong(next());
        }
        public Double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}