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.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        ArrayList<ArrayList<Integer>> edge = new ArrayList<ArrayList<Integer>>();
        for (int i=0;i<N;i++) {
            ArrayList<Integer> add = new ArrayList<Integer>();
            edge.add(add);
        }
        for (int i=0;i<N-1;i++) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            edge.get(a).add(b);
            edge.get(b).add(a);
        }

        int[] dist = new int[N];
        Arrays.fill(dist, -1);

        ArrayDeque<int[]> q = new ArrayDeque<int[]>();
        int[] first = {0, 0};
        q.add(first);
        while (!q.isEmpty()) {
            int[] rem = q.poll();
            if (dist[rem[0]]!=-1) continue;
            dist[rem[0]] = rem[1];
            for (Integer i : edge.get(rem[0])) {
                int[] add = {i, rem[1]+1};
                if (dist[i]==-1) q.add(add);
            }
        }
        // System.out.println(Arrays.toString(dist));
        HashSet<Integer> zero = new HashSet<Integer>();
        HashSet<Integer> one = new HashSet<Integer>();
        for (int i=0;i<N;i++) {
            dist[i]%=2;
            if (dist[i]==0) zero.add(i);
            if (dist[i]==1) one.add(i);
        }
        // System.out.println(zero);
        // System.out.println(one);
        if (zero.size()>one.size()) {
            HashSet<Integer> tmp = new HashSet<Integer>(zero);
            zero = one;
            one = tmp;
        }
        int[] ans = new int[N];
        HashSet<Integer> nums = new HashSet<Integer>();
        for (int i=1;i<=N;i++) {
            nums.add(i);
        }
        HashSet<Integer> index = new HashSet<Integer>();
        for (int i=0;i<N;i++) {
            index.add(i);
        }
        if (zero.size()<=N/3) {
            int num = 3;
            for (Integer i : zero) {
                ans[i] = num;
                nums.remove(num);
                index.remove(i);
                num+=3;
            }
            ArrayList<Integer> nums_list = new ArrayList<Integer>(nums);
            ArrayList<Integer> index_list = new ArrayList<Integer>(index);
            for (int i=0;i<nums_list.size();i++) {
                ans[index_list.get(i)] = nums_list.get(i);
            }
            StringBuilder sb = new StringBuilder();
            for (int i=0;i<N;i++) {
                sb.append(ans[i]);
                if (i!=N-1) sb.append(" ");
            }
            System.out.println(sb);
        } else {
            int num = 1;
            HashSet<Integer> zero_tmp = new HashSet<Integer>(zero);
            for (Integer i : zero_tmp) {
                ans[i] = num;
                nums.remove(num);
                index.remove(i);
                zero.remove(i);
                num+=3;
                if (num>N) break;
            }
            num = 3;
            for (Integer i : zero) {
                ans[i] = num;
                nums.remove(num);
                index.remove(i);
                // zero.remove(i);
                num+=3;
            }
            ArrayList<Integer> nums_list = new ArrayList<Integer>(nums);
            ArrayList<Integer> index_list = new ArrayList<Integer>(index);
            for (int i=0;i<nums_list.size();i++) {
                ans[index_list.get(i)] = nums_list.get(i);
            }
            StringBuilder sb = new StringBuilder();
            for (int i=0;i<N;i++) {
                sb.append(ans[i]);
                if (i!=N-1) sb.append(" ");
            }
            System.out.println(sb);
        }
        // System.out.println(zero);
        // System.out.println(one);
    }
}