844_E. Upgrading Tree_36793
You are given a tree with n vertices and you are allowed to perform no more than 2n transformations on it. Transformation is defined by three vertices x, y, y' and consists of deleting edge (x, y) and adding edge (x, y'). Transformation x, y, y' could be performed if all the following conditions are satisfied:

  1. There is an edge (x, y) in the current tree. 
  2. After the transformation the graph remains a tree. 
  3. After the deletion of edge (x, y) the tree would consist of two connected components. Let's denote the set of nodes in the component containing vertex x by Vx, and the set of nodes in the component containing vertex y by Vy. Then condition |Vx| > |Vy| should be satisfied, i.e. the size of the component with x should be strictly larger than the size of the component with y. 



You should minimize the sum of squared distances between all pairs of vertices in a tree, which you could get after no more than 2n transformations and output any sequence of transformations leading initial tree to such state.

Note that you don't need to minimize the number of operations. It is necessary to minimize only the sum of the squared distances.

Input

The first line of input contains integer n (1 ≤ n ≤ 2·105) — number of vertices in tree.

The next n - 1 lines of input contains integers a and b (1 ≤ a, b ≤ n, a ≠ b) — the descriptions of edges. It is guaranteed that the given edges form a tree.

Output

In the first line output integer k (0 ≤ k ≤ 2n) — the number of transformations from your example, minimizing sum of squared distances between all pairs of vertices.

In each of the next k lines output three integers x, y, y' — indices of vertices from the corresponding transformation.

Transformations with y = y' are allowed (even though they don't change tree) if transformation conditions are satisfied.

If there are several possible answers, print any of them.

Examples

Input

3
3 2
1 3


Output

0


Input

7
1 2
2 3
3 4
4 5
5 6
6 7


Output

2
4 3 2
4 5 6

Note

This is a picture for the second sample. Added edges are dark, deleted edges are dotted.

<image>
import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        dfs1(1, -1);
        int[] a = new int[2];
        int mx = n + 1;
        for (int i = 1; i <= n; i++) {
            if (msz[i] < mx) {
                mx = msz[i];
                a[0] = i;
                a[1] = -1;
            } else if (msz[i] == mx) {
                a[1] = i;
            }
        }
        root = a[0];
        for (int v : g[a[0]]) {
            if (v != a[1]) {
                goal = last = v;
                dfs2(v, a[0]);
                add(a[0], last, v);
            }
        }
        if (a[1] != -1) {
            root = a[1];
            for (int v : g[a[1]]) {
                if (v != a[0]) {
                    goal = last = v;
                    dfs2(v, a[1]);
                    add(a[1], last, v);
                }
            }
        }
        out.println(ans.size());
        for (int[] arr : ans) {
            out.println(arr[0] + " " + arr[1] + " " + arr[2]);
        }
        out.close();
    }

    static ArrayList<Integer>[] g = new ArrayList[200001];
    static int[] msz = new int[200001];
    static int[] sz = new int[200001];
    static int n;
    static ArrayList<int[]> ans = new ArrayList<>();
    static int goal;
    static int root;
    static int last;

    static void add(int x, int y, int z) {
        int[] t = {x, y, z};
        ans.add(t);
    }

    static void dfs1(int u, int fa) {
        sz[u] = 1;
        for (int v : g[u]) {
            if (v != fa) {
                dfs1(v, u);
                sz[u] += sz[v];
                msz[u] = Math.max(msz[u], sz[v]);
            }
        }
        msz[u] = Math.max(msz[u], n - sz[u]);
    }

    static void dfs2(int u, int fa) {
        if (u != goal) {
            add(root, last, u);
            add(u, fa, goal);
            last = u;
        }
        for (int v : g[u]) {
            if (v != fa) {
                dfs2(v, u);
            }
        }

    }

    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());
        }

    }
}

3
3 2
1 3
 7
1 2
2 3
3 4
4 5
5 6
6 7
 9
9 2
9 3
9 4
9 5
2 6
5 7
7 8
7 1
 9
7 2
7 3
7 4
7 5
2 6
5 1
1 8
1 9
 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
 10
6 9
9 2
4 7
5 4
7 9
8 5
9 10
2 1
8 3
 9
3 2
3 1
3 4
3 5
2 6
5 7
7 8
7 9
 9
8 2
8 3
8 4
8 5
2 6
5 7
7 1
7 9
 7
1 2
2 3
3 4
4 5
5 6
6 7
 50
28 44
19 36
15 20
49 33
27 18
48 34
5 35
31 3
32 25
22 33
8 7
3 49
32 12
34 29
4 24
5 41
17 24
43 27
11 22
6 33
32 28
27 22
10 43
39 9
45 14
32 46
28 45
7 37
47 42
42 33
5 21
40 39
9 25
23 8
10 29
7 4
41 50
26 33
49 17
12 24
1 8
17 19
41 16
42 20
30 34
13 7
38 29
7 50
19 2
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12
9 13
9 14
12 15
12 16
 9
1 2
1 3
1 4
1 5
2 6
5 7
7 8
7 9
 9
4 2
4 3
4 1
4 5
2 6
5 7
7 8
7 9
 10
10 1
1 4
4 2
2 3
3 6
6 9
9 5
5 8
8 7
 9
2 1
2 3
2 4
2 5
1 6
5 7
7 8
7 9
 9
5 2
5 3
5 4
5 1
2 6
1 7
7 8
7 9
 9
6 2
6 3
6 4
6 5
2 1
5 7
7 8
7 9
 12
1 3
3 2
3 4
4 5
4 7
7 6
7 8
8 9
8 10
9 11
9 12
 14
1 2
2 14
2 3
3 4
4 5
5 6
5 7
4 10
10 9
10 8
3 11
11 13
11 12
 5
1 2
1 3
2 4
2 5
 9
9 2
9 3
9 4
9 5
2 6
5 7
10 8
7 1
 10
1 2
4 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
 9
8 2
8 3
8 4
8 9
2 6
5 7
7 1
7 9
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
1 12
9 13
9 14
12 15
12 16
 10
10 1
1 3
4 2
2 3
3 6
6 9
9 5
5 8
8 7
 9
2 1
2 3
2 4
3 5
1 6
5 7
7 8
7 9
 9
5 2
5 3
4 4
5 1
2 6
1 7
7 8
7 9
 9
6 1
6 3
6 4
6 5
2 1
5 7
7 8
7 9
 14
1 2
2 17
2 3
3 4
4 5
5 6
5 7
4 10
10 9
10 8
3 11
11 13
11 12
 5
1 2
2 3
2 4
2 5
 3
3 2
2 3
 9
9 2
9 3
9 4
9 5
2 6
5 10
10 8
7 1
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
1 12
9 13
9 14
14 15
12 16
 10
10 1
1 3
4 2
2 3
3 6
6 9
9 5
10 8
8 7
 9
5 2
5 3
4 4
5 1
2 6
1 7
7 8
4 9
 9
6 1
6 3
6 4
4 5
2 1
5 7
7 8
7 9
 5
1 2
2 3
1 4
2 5
 10
1 2
4 3
3 4
2 5
5 6
6 7
7 8
8 9
12 10
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
5 11
1 12
9 13
9 14
14 15
12 16
 10
10 1
1 3
4 2
2 1
3 6
6 9
9 5
10 8
8 7
 9
5 2
5 3
8 4
5 1
2 6
1 7
7 8
4 9
 9
5 2
5 3
8 4
5 1
2 6
1 7
7 8
4 10
 10
1 2
0 3
3 4
2 5
5 9
6 7
7 8
8 9
12 10
 10
1 2
0 3
1 4
2 5
5 9
6 7
7 8
8 9
12 10
 10
1 2
0 3
1 4
1 5
5 9
6 7
7 8
8 9
12 10
 10
1 2
0 3
1 4
1 7
5 9
6 7
7 8
8 9
12 10
 9
9 2
9 3
9 4
9 5
2 6
5 7
4 8
7 1
 9
7 2
7 3
7 4
7 5
2 6
5 2
1 8
1 9
 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
0 10
 10
6 15
9 2
4 7
5 4
7 9
8 5
9 10
2 1
8 3
 7
1 2
2 3
3 4
4 9
5 6
6 7
 50
28 44
19 36
15 20
49 33
42 18
48 34
5 35
31 3
32 25
22 33
8 7
3 49
32 12
34 29
4 24
5 41
17 24
43 27
11 22
6 33
32 28
27 22
10 43
39 9
45 14
32 46
28 45
7 37
47 42
42 33
5 21
40 39
9 25
23 8
10 29
7 4
41 50
26 33
49 17
12 24
1 8
17 19
41 16
42 20
30 34
13 7
38 29
7 50
19 2
 10
10 1
1 4
4 2
2 3
3 6
6 9
9 5
5 8
8 12
 9
1 2
5 3
5 4
5 1
2 6
1 7
7 8
7 9
 9
6 2
6 3
6 4
6 5
2 1
5 7
7 8
12 9
 12
1 3
3 2
3 5
4 5
4 7
7 6
7 8
8 9
8 10
9 11
9 12
 14
1 2
2 14
2 3
3 4
4 5
5 6
5 7
4 10
10 9
10 8
5 11
11 13
11 12
 5
1 2
1 3
3 4
2 5
 3
3 4
1 3
 7
1 2
2 3
3 4
4 5
5 6
6 8
 9
9 2
9 3
9 4
9 5
2 6
5 7
10 8
6 1
 9
8 2
8 3
8 4
8 9
2 6
10 7
7 1
7 9
 10
10 1
1 3
4 2
2 3
3 6
6 9
9 5
5 8
3 7
 9
2 1
2 3
2 4
3 5
1 6
5 7
7 8
6 9
 9
6 1
6 3
6 4
6 5
2 1
5 8
7 8
7 9
 14
1 2
2 17
2 4
3 4
4 5
5 6
5 7
4 10
10 9
10 8
3 11
11 13
11 12
 5
1 2
2 3
2 1
2 5
 9
9 2
9 3
9 4
9 5
2 6
5 10
10 8
13 1
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
1 12
9 17
9 14
14 15
12 16
 9
6 1
6 3
6 4
4 5
2 2
5 7
7 8
7 9
 5
1 2
2 3
1 4
1 5
 10
1 2
4 3
3 4
2 5
5 6
6 7
4 8
8 9
12 10
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 17
5 10
5 11
1 12
9 13
9 14
14 15
12 16
 9
5 2
5 3
8 4
5 1
2 6
1 7
7 8
2 9
 9
1 2
5 3
8 4
5 1
2 6
1 7
7 8
4 10
 10
1 2
0 3
1 4
1 7
5 8
6 7
7 8
8 9
12 14
 10
1 2
2 3
3 4
4 5
5 6
6 7
11 8
8 9
0 10
 10
6 15
9 2
4 7
5 4
7 9
8 5
16 10
2 1
8 3
 7
1 2
2 3
5 4
4 9
5 6
6 7
 50
28 44
19 36
15 20
49 33
42 18
48 34
5 35
31 3
32 25
22 33
8 3
3 49
32 12
34 29
4 24
5 41
17 24
43 27
11 22
6 33
32 28
27 22
10 43
39 9
45 14
32 46
28 45
7 37
47 42
42 33
5 21
40 39
9 25
23 8
10 29
7 4
41 50
26 33
49 17
12 24
1 8
17 19
41 16
42 20
30 34
13 7
38 29
7 50
19 2
 10
10 1
1 4
4 2
2 3
3 6
6 9
9 5
5 8
9 12
 9
6 2
6 3
6 4
9 5
2 1
5 7
7 8
12 9
 12
1 3
3 2
1 5
4 5
4 7
7 6
7 8
8 9
8 10
9 11
9 12
 14
1 2
2 14
1 3
3 4
4 5
5 6
5 7
4 10
10 9
10 8
5 11
11 13
11 12
 5
1 2
1 3
3 4
2 1
 9
9 2
9 3
9 4
9 5
2 6
5 13
10 8
6 1
 9
6 1
12 3
6 4
6 5
2 1
5 8
7 8
7 9
 14
1 2
2 17
2 4
3 4
4 5
5 6
5 7
4 10
10 9
10 8
3 11
11 13
3 12
 3
4 1
2 3
 9
6 1
6 3
6 4
4 5
2 2
5 7
7 8
8 9
 5
1 2
2 3
1 0
1 5
 16
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 17
5 10
5 11
1 12
9 13
9 16
14 15
12 16
 9
5 2
5 3
8 4
5 1
2 6
1 13
7 8
2 9
 10
1 2
0 3
3 4
2 8
5 6
6 7
7 8
8 9
14 10
 10
1 2
0 2
1 4
1 7
5 8
6 7
7 8
8 9
12 14
 10
1 2
2 3
3 4
4 5
5 6
6 7
11 8
5 9
0 10
 10
6 15
9 2
7 7
5 4
7 9
8 5
16 10
2 1
8 3
 10
10 1
1 4
4 2
2 3
3 6
9 9
9 5
5 8
9 12
 12
1 3
3 2
1 5
4 5
4 7
7 6
7 8
8 9
8 10
9 11
9 15
 14
1 2
2 14
1 3
3 4
4 5
5 6
5 7
4 10
10 9
17 8
5 11
11 13
11 12
 5
1 2
1 3
3 7
2 1
 9
9 2
2 3
9 4
9 5
2 6
5 13
10 8
6 1
 9
6 1
12 3
6 4
12 5
2 1
5 8
7 8
7 9
 3
3 1
2 3
 9
9 2
9 3
9 4
14 5
1 6
5 10
10 8
13 1
 9
6 1
6 3
6 4
1 5
2 2
5 7
7 8
8 9
 5
1 2
2 3
1 0
1 7
 16
1 4
1 3
2 4
3 5
3 6
4 7
4 8
5 17
5 10
5 11
1 12
9 13
9 16
14 15
12 16
 9
5 2
5 3
8 4
5 1
2 6
1 26
7 8
2 9
 10
1 2
2 3
3 4
4 5
5 6
1 7
11 8
5 9
0 10
 14
1 2
2 14
1 3
3 4
4 5
5 6
4 7
4 10
10 9
17 8
5 11
11 13
11 12
 5
1 2
1 3
6 7
2 1
 9
6 1
12 3
6 4
12 5
2 1
5 8
7 2
7 9
 3
1 1
2 3
 9
5 2
5 3
8 4
6 1
2 6
1 26
7 8
2 9
 10
1 2
2 3
3 4
4 5
5 6
1 7
6 8
5 9
0 10
 10
10 1
1 4
4 2
2 5
3 6
9 18
9 5
5 8
9 12
 9
6 1
12 3
6 4
12 5
2 1
5 8
7 2
9 9
 16
1 4
1 3
2 4
3 5
3 6
4 7
4 8
2 17
5 10
5 11
1 12
9 13
9 16
14 25
12 16
 9
5 2
5 3
8 4
6 1
4 6
1 26
7 8
2 9

2
3 2 2
3 1 1
 10
4 3 1
1 2 3
4 1 2
2 3 3
4 2 3
4 5 7
7 6 5
4 7 6
6 5 5
4 6 5
 12
9 2 6
6 2 2
9 6 2
9 3 3
9 4 4
9 5 8
8 7 5
9 8 1
1 7 5
9 1 7
7 5 5
9 7 5
 12
7 2 6
6 2 2
7 6 2
7 3 3
7 4 4
7 5 8
8 1 5
7 8 9
9 1 5
7 9 1
1 5 5
7 1 5
 14
5 4 1
1 2 4
5 1 2
2 3 4
5 2 3
3 4 4
5 3 4
6 7 10
10 9 7
6 10 9
9 8 7
6 9 8
8 7 7
6 8 7
 12
9 6 6
9 2 1
1 2 2
9 1 2
9 10 10
7 4 3
3 8 4
7 3 8
8 5 4
7 8 5
5 4 4
7 5 4
 12
3 2 6
6 2 2
3 6 2
3 1 1
3 4 4
3 5 8
8 7 5
3 8 9
9 7 5
3 9 7
7 5 5
3 7 5
 12
8 2 6
6 2 2
8 6 2
8 3 3
8 4 4
8 5 1
1 7 5
8 1 9
9 7 5
8 9 7
7 5 5
8 7 5
 10
4 3 1
1 2 3
4 1 2
2 3 3
4 2 3
4 5 7
7 6 5
4 7 6
6 5 5
4 6 5
 92
24 4 23
23 8 4
24 23 1
1 8 4
24 1 8
8 7 4
24 8 37
37 7 4
24 37 13
13 7 4
24 13 35
35 5 4
24 35 21
21 5 4
24 21 5
5 41 4
24 5 16
16 41 4
24 16 41
41 50 4
24 41 50
50 7 4
24 50 7
7 4 4
24 7 4
24 12 40
40 39 12
24 40 39
39 9 12
24 39 9
9 25 12
24 9 25
25 32 12
24 25 44
44 28 12
24 44 14
14 45 12
24 14 45
45 28 12
24 45 28
28 32 12
24 28 46
46 32 12
24 46 32
32 12 12
24 32 12
17 49 11
11 22 49
17 11 18
18 27 49
17 18 48
48 34 49
17 48 30
30 34 49
17 30 34
34 29 49
17 34 38
38 29 49
17 38 29
29 10 49
17 29 10
10 43 49
17 10 43
43 27 49
17 43 27
27 22 49
17 27 22
22 33 49
17 22 6
6 33 49
17 6 47
47 42 49
17 47 15
15 20 49
17 15 20
20 42 49
17 20 42
42 33 49
17 42 26
26 33 49
17 26 33
33 49 49
17 33 31
31 3 49
17 31 3
3 49 49
17 3 49
17 19 36
36 19 19
17 36 2
2 19 19
17 2 19
 27
3 1 7
7 4 1
3 7 8
8 4 1
3 8 4
4 2 1
3 4 2
2 1 1
3 2 1
3 5 13
13 9 5
3 13 14
14 9 5
3 14 9
9 5 5
3 9 10
10 5 5
3 10 5
3 6 11
11 6 6
3 11 15
15 12 6
3 15 16
16 12 6
3 16 12
12 6 6
3 12 6
 12
1 2 6
6 2 2
1 6 2
1 3 3
1 4 4
1 5 8
8 7 5
1 8 9
9 7 5
1 9 7
7 5 5
1 7 5
 12
4 2 6
6 2 2
4 6 2
4 3 3
4 1 1
4 5 8
8 7 5
4 8 9
9 7 5
4 9 7
7 5 5
4 7 5
 14
3 2 10
10 1 2
3 10 1
1 4 2
3 1 4
4 2 2
3 4 2
6 9 7
7 8 9
6 7 8
8 5 9
6 8 5
5 9 9
6 5 9
 12
2 1 6
6 1 1
2 6 1
2 3 3
2 4 4
2 5 8
8 7 5
2 8 9
9 7 5
2 9 7
7 5 5
2 7 5
 12
5 2 6
6 2 2
5 6 2
5 3 3
5 4 4
5 1 8
8 7 1
5 8 9
9 7 1
5 9 7
7 1 1
5 7 1
 12
6 2 1
1 2 2
6 1 2
6 3 3
6 4 4
6 5 8
8 7 5
6 8 9
9 7 5
6 9 7
7 5 5
6 7 5
 19
7 4 1
1 3 4
7 1 2
2 3 4
7 2 3
3 4 4
7 3 5
5 4 4
7 5 4
7 6 6
7 8 11
11 9 8
7 11 12
12 9 8
7 12 9
9 8 8
7 9 10
10 8 8
7 10 8
 20
3 2 1
1 2 2
3 1 14
14 2 2
3 14 2
3 11 13
13 11 11
3 13 12
12 11 11
3 12 11
4 5 6
6 5 5
4 6 7
7 5 5
4 7 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 5
2 1 3
3 1 1
2 3 1
2 4 4
2 5 5
 10
9 2 6
6 2 2
9 6 2
9 3 3
9 4 4
9 5 1
1 7 5
9 1 7
7 5 5
9 7 5
 1
1 2 2
 12
8 2 6
6 2 2
8 6 2
8 3 3
8 4 4
8 9 5
5 7 9
8 5 1
1 7 9
8 1 7
7 9 9
8 7 9
 24
1 2 7
7 4 2
1 7 8
8 4 2
1 8 4
4 2 2
1 4 2
1 12 15
15 12 12
1 15 16
16 12 12
1 16 12
3 5 13
13 9 5
3 13 14
14 9 5
3 14 9
9 5 5
3 9 10
10 5 5
3 10 5
3 6 11
11 6 6
3 11 6
 13
3 1 10
10 1 1
3 10 1
3 2 4
4 2 2
3 4 2
6 9 7
7 8 9
6 7 8
8 5 9
6 8 5
5 9 9
6 5 9
 14
3 2 6
6 1 2
3 6 1
1 2 2
3 1 4
4 2 2
3 4 2
3 5 8
8 7 5
3 8 9
9 7 5
3 9 7
7 5 5
3 7 5
 12
1 5 6
6 2 5
1 6 2
2 5 5
1 2 3
3 5 5
1 3 5
1 7 8
8 7 7
1 8 9
9 7 7
1 9 7
 12
6 1 2
2 1 1
6 2 1
6 3 3
6 4 4
6 5 8
8 7 5
6 8 9
9 7 5
6 9 7
7 5 5
6 7 5
 20
3 2 1
1 2 2
3 1 17
17 2 2
3 17 2
3 11 13
13 11 11
3 13 12
12 11 11
3 12 11
4 5 6
6 5 5
4 6 7
7 5 5
4 7 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 4
2 1 1
2 3 3
2 4 4
2 5 5
 0
 1
1 7 7
 27
3 1 7
7 4 1
3 7 8
8 4 1
3 8 4
4 2 1
3 4 2
2 1 1
3 2 16
16 12 1
3 16 12
12 1 1
3 12 1
3 5 13
13 9 5
3 13 15
15 14 5
3 15 14
14 9 5
3 14 9
9 5 5
3 9 10
10 5 5
3 10 5
3 6 11
11 6 6
3 11 6
 15
3 1 7
7 8 1
3 7 8
8 10 1
3 8 10
10 1 1
3 10 1
3 2 4
4 2 2
3 4 2
3 6 5
5 9 6
3 5 9
9 6 6
3 9 6
 10
1 5 6
6 2 5
1 6 2
2 5 5
1 2 3
3 5 5
1 3 5
1 7 8
8 7 7
1 8 7
 14
4 6 2
2 1 6
4 2 1
1 6 6
4 1 3
3 6 6
4 3 6
4 5 8
8 7 5
4 8 9
9 7 5
4 9 7
7 5 5
4 7 5
 5
2 1 4
4 1 1
2 4 1
2 3 3
2 5 5
 8
2 1 1
5 6 9
9 8 6
5 9 8
8 7 6
5 8 7
7 6 6
5 7 6
 27
3 1 7
7 4 1
3 7 8
8 4 1
3 8 4
4 2 1
3 4 2
2 1 1
3 2 16
16 12 1
3 16 12
12 1 1
3 12 1
3 5 13
13 9 5
3 13 15
15 14 5
3 15 14
14 9 5
3 14 9
9 5 5
3 9 10
10 5 5
3 10 11
11 5 5
3 11 5
3 6 6
 15
1 10 7
7 8 10
1 7 8
8 10 10
1 8 10
1 3 5
5 9 3
1 5 9
9 6 3
1 9 6
6 3 3
1 6 3
1 2 4
4 2 2
1 4 2
 14
1 5 6
6 2 5
1 6 2
2 5 5
1 2 3
3 5 5
1 3 5
1 7 9
9 4 7
1 9 4
4 8 7
1 4 8
8 7 7
1 8 7
 14
1 5 6
6 2 5
1 6 2
2 5 5
1 2 3
3 5 5
1 3 5
1 7 10
10 4 7
1 10 4
4 8 7
1 4 8
8 7 7
1 8 7
 8
2 1 1
5 9 6
6 7 9
5 6 7
7 8 9
5 7 8
8 9 9
5 8 9
 10
2 1 4
4 1 1
2 4 1
5 9 6
6 7 9
5 6 7
7 8 9
5 7 8
8 9 9
5 8 9
 9
1 2 2
1 4 4
5 9 6
6 7 9
5 6 7
7 8 9
5 7 8
8 9 9
5 8 9
 8
1 2 2
1 4 4
7 6 6
7 8 5
5 9 8
7 5 9
9 8 8
7 9 8
 12
9 2 6
6 2 2
9 6 2
9 3 3
9 4 8
8 4 4
9 8 4
9 5 1
1 7 5
9 1 7
7 5 5
9 7 5
 2
1 8 8
1 9 9
 12
4 3 1
1 2 3
4 1 2
2 3 3
4 2 3
5 6 9
9 8 6
5 9 8
8 7 6
5 8 7
7 6 6
5 7 6
 11
9 2 1
1 2 2
9 1 2
9 10 10
7 4 3
3 8 4
7 3 8
8 5 4
7 8 5
5 4 4
7 5 4
 6
2 1 1
2 3 9
9 4 3
2 9 4
4 3 3
2 4 3
 92
24 4 23
23 8 4
24 23 1
1 8 4
24 1 8
8 7 4
24 8 37
37 7 4
24 37 13
13 7 4
24 13 35
35 5 4
24 35 21
21 5 4
24 21 5
5 41 4
24 5 16
16 41 4
24 16 41
41 50 4
24 41 50
50 7 4
24 50 7
7 4 4
24 7 4
24 12 40
40 39 12
24 40 39
39 9 12
24 39 9
9 25 12
24 9 25
25 32 12
24 25 44
44 28 12
24 44 14
14 45 12
24 14 45
45 28 12
24 45 28
28 32 12
24 28 46
46 32 12
24 46 32
32 12 12
24 32 12
17 49 11
11 22 49
17 11 48
48 34 49
17 48 30
30 34 49
17 30 34
34 29 49
17 34 38
38 29 49
17 38 29
29 10 49
17 29 10
10 43 49
17 10 43
43 27 49
17 43 27
27 22 49
17 27 22
22 33 49
17 22 6
6 33 49
17 6 18
18 42 49
17 18 47
47 42 49
17 47 15
15 20 49
17 15 20
20 42 49
17 20 42
42 33 49
17 42 26
26 33 49
17 26 33
33 49 49
17 33 31
31 3 49
17 31 3
3 49 49
17 3 49
17 19 36
36 19 19
17 36 2
2 19 19
17 2 19
 14
3 2 10
10 1 2
3 10 1
1 4 2
3 1 4
4 2 2
3 4 2
6 9 12
12 8 9
6 12 8
8 5 9
6 8 5
5 9 9
6 5 9
 13
1 2 6
6 2 2
1 6 2
1 5 3
3 5 5
1 3 4
4 5 5
1 4 5
1 7 8
8 7 7
1 8 9
9 7 7
1 9 7
 10
6 2 1
1 2 2
6 1 2
6 3 3
6 4 4
6 5 8
8 7 5
6 8 7
7 5 5
6 7 5
 19
7 4 1
1 3 4
7 1 2
2 3 4
7 2 3
3 5 4
7 3 5
5 4 4
7 5 4
7 6 6
7 8 11
11 9 8
7 11 12
12 9 8
7 12 9
9 8 8
7 9 10
10 8 8
7 10 8
 23
4 3 1
1 2 3
4 1 14
14 2 3
4 14 2
2 3 3
4 2 3
4 5 6
6 5 5
4 6 7
7 5 5
4 7 13
13 11 5
4 13 12
12 11 5
4 12 11
11 5 5
4 11 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 6
1 2 5
5 2 2
1 5 2
1 3 4
4 3 3
1 4 3
 2
3 4 4
3 1 1
 10
4 3 1
1 2 3
4 1 2
2 3 3
4 2 3
4 5 8
8 6 5
4 8 6
6 5 5
4 6 5
 10
9 2 1
1 6 2
9 1 6
6 2 2
9 6 2
9 3 3
9 4 4
9 5 7
7 5 5
9 7 5
 12
8 2 6
6 2 2
8 6 2
8 3 3
8 4 4
8 9 10
10 7 9
8 10 1
1 7 9
8 1 7
7 9 9
8 7 9
 14
3 1 10
10 1 1
3 10 1
3 2 4
4 2 2
3 4 2
3 6 8
8 5 6
3 8 5
5 9 6
3 5 9
9 6 6
3 9 6
3 7 7
 13
2 1 9
9 6 1
2 9 6
6 1 1
2 6 1
2 3 8
8 7 3
2 8 7
7 5 3
2 7 5
5 3 3
2 5 3
2 4 4
 12
6 1 2
2 1 1
6 2 1
6 3 3
6 4 4
6 5 9
9 7 5
6 9 7
7 8 5
6 7 8
8 5 5
6 8 5
 22
4 2 1
1 2 2
4 1 17
17 2 2
4 17 2
4 3 13
13 11 3
4 13 12
12 11 3
4 12 11
11 3 3
4 11 3
4 5 6
6 5 5
4 6 7
7 5 5
4 7 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 4
2 1 1
2 3 3
2 1 1
2 5 5
 1
1 13 13
 27
3 1 7
7 4 1
3 7 8
8 4 1
3 8 4
4 2 1
3 4 2
2 1 1
3 2 16
16 12 1
3 16 12
12 1 1
3 12 1
3 5 17
17 9 5
3 17 15
15 14 5
3 15 14
14 9 5
3 14 9
9 5 5
3 9 10
10 5 5
3 10 5
3 6 11
11 6 6
3 11 6
 12
4 6 1
1 6 6
4 1 3
3 6 6
4 3 6
4 5 8
8 7 5
4 8 9
9 7 5
4 9 7
7 5 5
4 7 5
 5
1 2 3
3 2 2
1 3 2
1 4 4
1 5 5
 7
1 2 7
7 6 2
1 7 6
6 5 2
1 6 5
5 2 2
1 5 2
 21
1 2 7
7 4 2
1 7 8
8 4 2
1 8 4
4 2 2
1 4 2
1 3 17
17 5 3
1 17 10
10 5 3
1 10 11
11 5 3
1 11 5
5 3 3
1 5 6
6 3 3
1 6 3
1 12 16
16 12 12
1 16 12
 13
5 2 6
6 2 2
5 6 9
9 2 2
5 9 2
5 3 3
5 1 4
4 8 1
5 4 8
8 7 1
5 8 7
7 1 1
5 7 1
 13
1 2 6
6 2 2
1 6 2
1 5 3
3 5 5
1 3 5
1 7 10
10 4 7
1 10 4
4 8 7
1 4 8
8 7 7
1 8 7
 8
1 2 2
1 4 4
7 6 6
7 8 5
5 8 8
7 5 9
9 8 8
7 9 8
 8
2 1 1
3 4 7
7 6 4
3 7 6
6 5 4
3 6 5
5 4 4
3 5 4
 10
9 2 1
1 2 2
9 1 2
7 4 3
3 8 4
7 3 8
8 5 4
7 8 5
5 4 4
7 5 4
 3
1 2 3
3 2 2
1 3 2
 95
17 24 37
37 7 24
17 37 13
13 7 24
17 13 35
35 5 24
17 35 21
21 5 24
17 21 5
5 41 24
17 5 16
16 41 24
17 16 41
41 50 24
17 41 50
50 7 24
17 50 7
7 4 24
17 7 4
4 24 24
17 4 40
40 39 24
17 40 39
39 9 24
17 39 9
9 25 24
17 9 25
25 32 24
17 25 44
44 28 24
17 44 14
14 45 24
17 14 45
45 28 24
17 45 28
28 32 24
17 28 46
46 32 24
17 46 32
32 12 24
17 32 12
12 24 24
17 12 24
17 49 11
11 22 49
17 11 48
48 34 49
17 48 30
30 34 49
17 30 34
34 29 49
17 34 38
38 29 49
17 38 29
29 10 49
17 29 10
10 43 49
17 10 43
43 27 49
17 43 27
27 22 49
17 27 22
22 33 49
17 22 6
6 33 49
17 6 18
18 42 49
17 18 47
47 42 49
17 47 15
15 20 49
17 15 20
20 42 49
17 20 42
42 33 49
17 42 26
26 33 49
17 26 33
33 49 49
17 33 31
31 3 49
17 31 23
23 8 49
17 23 1
1 8 49
17 1 8
8 3 49
17 8 3
3 49 49
17 3 49
17 19 36
36 19 19
17 36 2
2 19 19
17 2 19
 14
3 2 10
10 1 2
3 10 1
1 4 2
3 1 4
4 2 2
3 4 2
6 9 8
8 5 9
6 8 5
5 9 9
6 5 12
12 9 9
6 12 9
 7
1 2 3
3 6 2
1 3 4
4 6 2
1 4 6
6 2 2
1 6 2
 19
7 4 2
2 3 4
7 2 3
3 1 4
7 3 1
1 5 4
7 1 5
5 4 4
7 5 4
7 6 6
7 8 11
11 9 8
7 11 12
12 9 8
7 12 9
9 8 8
7 9 10
10 8 8
7 10 8
 23
4 3 14
14 2 3
4 14 2
2 1 3
4 2 1
1 3 3
4 1 3
4 5 6
6 5 5
4 6 7
7 5 5
4 7 13
13 11 5
4 13 12
12 11 5
4 12 11
11 5 5
4 11 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 5
1 2 2
1 3 4
4 3 3
1 4 3
1 2 2
 10
9 2 1
1 6 2
9 1 6
6 2 2
9 6 2
9 3 3
9 4 4
9 5 13
13 5 5
9 13 5
 11
6 1 2
2 1 1
6 2 1
6 4 4
6 5 9
9 7 5
6 9 7
7 8 5
6 7 8
8 5 5
6 8 5
 22
4 2 1
1 2 2
4 1 17
17 2 2
4 17 2
4 3 13
13 11 3
4 13 11
11 3 3
4 11 12
12 3 3
4 12 3
4 5 6
6 5 5
4 6 7
7 5 5
4 7 5
4 10 9
9 10 10
4 9 8
8 10 10
4 8 10
 1
1 4 4
 12
4 6 1
1 6 6
4 1 3
3 6 6
4 3 6
4 5 9
9 8 5
4 9 8
8 7 5
4 8 7
7 5 5
4 7 5
 4
1 2 3
3 2 2
1 3 2
1 5 5
 25
1 2 7
7 4 2
1 7 8
8 4 2
1 8 4
4 2 2
1 4 2
1 3 17
17 5 3
1 17 10
10 5 3
1 10 11
11 5 3
1 11 5
5 3 3
1 5 6
6 3 3
1 6 3
1 12 13
13 9 12
1 13 9
9 16 12
1 9 16
16 12 12
1 16 12
 9
5 2 6
6 2 2
5 6 9
9 2 2
5 9 2
5 3 3
5 1 13
13 1 1
5 13 1
 7
2 1 1
8 7 5
5 6 7
8 5 6
6 7 7
8 6 7
8 9 9
 10
1 2 0
0 2 2
1 0 2
1 4 4
7 6 6
7 8 5
5 8 8
7 5 9
9 8 8
7 9 8
 10
3 2 1
1 2 2
3 1 2
4 5 7
7 6 5
4 7 6
6 5 5
4 6 9
9 5 5
4 9 5
 21
1 2 1
1 2 2
1 1 2
2 9 2
1 2 9
9 7 2
1 9 7
7 7 2
1 7 1
1 2 2
1 1 2
2 9 2
1 2 9
9 7 2
1 9 7
7 7 2
1 7 7
7 9 2
1 7 9
9 2 2
1 9 2
 8
1 10 10
1 4 6
6 3 4
1 6 3
3 2 4
1 3 2
2 4 4
1 2 4
 19
7 4 2
2 3 4
7 2 3
3 1 4
7 3 1
1 5 4
7 1 5
5 4 4
7 5 4
7 6 6
7 8 11
11 9 8
7 11 15
15 9 8
7 15 9
9 8 8
7 9 10
10 8 8
7 10 8
 21
4 3 14
14 2 3
4 14 2
2 1 3
4 2 1
1 3 3
4 1 3
4 5 6
6 5 5
4 6 7
7 5 5
4 7 13
13 11 5
4 13 12
12 11 5
4 12 11
11 5 5
4 11 5
4 10 9
9 10 10
4 9 10
 5
1 2 2
1 3 7
7 3 3
1 7 3
1 2 2
 11
2 9 4
4 9 9
2 4 13
13 5 9
2 13 5
5 9 9
2 5 9
2 3 3
2 6 1
1 6 6
2 1 6
 4
1 6 4
4 6 6
1 4 6
1 2 2
 2
3 1 1
3 2 2
 2
1 6 6
1 13 13
 12
1 6 3
3 6 6
1 3 4
4 6 6
1 4 6
1 5 9
9 8 5
1 9 8
8 7 5
1 8 7
7 5 5
1 7 5
 4
1 2 3
3 2 2
1 3 2
1 7 7
 25
1 4 2
2 4 4
1 2 7
7 4 4
1 7 8
8 4 4
1 8 4
1 3 17
17 5 3
1 17 10
10 5 3
1 10 11
11 5 3
1 11 5
5 3 3
1 5 6
6 3 3
1 6 3
1 12 13
13 9 12
1 13 9
9 16 12
1 9 16
16 12 12
1 16 12
 9
5 2 6
6 2 2
5 6 9
9 2 2
5 9 2
5 3 3
5 1 26
26 1 1
5 26 1
 10
2 1 7
7 1 1
2 7 1
3 4 6
6 5 4
3 6 9
9 5 4
3 9 5
5 4 4
3 5 4
 20
4 3 14
14 2 3
4 14 2
2 1 3
4 2 1
1 3 3
4 1 3
4 5 6
6 5 5
4 6 13
13 11 5
4 13 12
12 11 5
4 12 11
11 5 5
4 11 5
4 7 7
4 10 9
9 10 10
4 9 10
 3
1 2 2
1 3 3
1 2 2
 8
1 6 4
4 6 6
1 4 6
1 2 9
9 7 2
1 9 7
7 2 2
1 7 2
 2
1 1 1
1 1 1
 10
6 1 26
26 1 1
6 26 1
6 2 3
3 5 2
6 3 5
5 2 2
6 5 9
9 2 2
6 9 2
 12
3 2 7
7 1 2
3 7 1
1 2 2
3 1 2
4 5 8
8 6 5
4 8 6
6 5 5
4 6 9
9 5 5
4 9 5
 11
2 4 10
10 1 4
2 10 1
1 4 4
2 1 4
5 9 18
18 9 9
5 18 12
12 9 9
5 12 9
5 8 8
 6
1 6 4
4 6 6
1 4 6
1 2 7
7 2 2
1 7 2
 25
1 4 17
17 2 4
1 17 2
2 4 4
1 2 7
7 4 4
1 7 8
8 4 4
1 8 4
1 3 10
10 5 3
1 10 11
11 5 3
1 11 5
5 3 3
1 5 6
6 3 3
1 6 3
1 12 13
13 9 12
1 13 9
9 16 12
1 9 16
16 12 12
1 16 12
 8
1 6 7
7 8 6
1 7 8
8 4 6
1 8 4
4 6 6
1 4 6
1 26 26
