Problem: You are given an unweighted tree with n vertices. Then n - 1 following operations are applied to the tree. A single operation consists of the following steps: 

  1. choose two leaves; 
  2. add the length of the simple path between them to the answer; 
  3. remove one of the chosen leaves from the tree. 



Initial answer (before applying operations) is 0. Obviously after n - 1 such operations the tree will consist of a single vertex. 

Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!

Input

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

Next n - 1 lines describe the edges of the tree in form ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). It is guaranteed that given graph is a tree.

Output

In the first line print one integer number — maximal possible answer. 

In the next n - 1 lines print the operations in order of their applying in format ai, bi, ci, where ai, bi — pair of the leaves that are chosen in the current operation (1 ≤ ai, bi ≤ n), ci (1 ≤ ci ≤ n, ci = ai or ci = bi) — choosen leaf that is removed from the tree in the current operation. 

See the examples for better understanding.

Examples

Input

3
1 2
1 3


Output

3
2 3 3
2 1 1


Input

5
1 2
1 3
2 4
2 5


Output

9
3 5 5
4 3 3
4 1 1
4 2 2

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class F {

    static class FastReader {
        StringTokenizer str;
        BufferedReader br;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            if (str == null || !str.hasMoreTokens()) {
                try {
                    str = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    return "";
                }
            }
            return str.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return next().charAt(0);
        }

        int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static class Graph {
        HashSet<Integer> adj[];
        boolean explored[];
        int[] dist1, dist2;
        int n, max = 0, i1 = 0, i2;
        long ans = 0;
        HashSet<Integer> route = new HashSet<>();
        StringBuilder temp = new StringBuilder();

        Graph(int n) {
            this.n = n;
            dist1 = new int[n];
            dist2 = new int[n];
            explored = new boolean[n];
            adj = new HashSet[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new HashSet<>();
            }
        }

        void addEdge(int u, int v) {
            adj[u].add(v);
            adj[v].add(u);
        }

        void dfs(int v, int l, int dist[]) {
            explored[v] = true;
            dist[v] = l;
            if (l > max) {
                max = l;
                i1 = v;
            }
            for (Integer i : adj[v]) {
                if (!explored[i]) {
                    dfs(i, l + 1, dist);
                }
            }
        }

        void dfs1(int v) {
            explored[v] = true;
            LinkedList<Integer> removed = new LinkedList<>();
            for (Integer i : adj[v]) {
                if (!explored[i]) {
                    dfs1(i);
                    if (adj[i].size() == 1 && i != i1 && i != i2) {
                        removed.add(i);
                        if (dist1[i] > dist2[i]) {
                            ans += dist1[i];
                            temp.append(i + 1).append(" ").append(i1 + 1).append(" ").append(i + 1).append("\n");
                        } else {
                            ans += dist2[i];
                            temp.append(i + 1).append(" ").append(i2 + 1).append(" ").append(i + 1).append("\n");
                        }
                    }
                }
            }
            adj[v].removeAll(removed);
        }

        void dfs2(int v) {
            if (v == i2)
                return;
            temp.append(v + 1).append(" ").append(i2 + 1).append(" ").append(v + 1).append("\n");
            ans += dist2[v];
            explored[v] = true;
            for (Integer i : adj[v]) {
                if (!explored[i]) {
                    adj[i].remove(v);
                    dfs2(i);
                }
            }
        }

        void dfs3(int v) {
            explored[v] = true;
            if (v == i1 || v == i2 || adj[v].size() > 1)
                return;
            if (dist1[v] > dist2[v]) {
                ans += dist1[v];
                temp.append(v + 1).append(" ").append(i1 + 1).append(" ").append(v + 1).append("\n");
            } else {
                ans += dist2[v];
                temp.append(v + 1).append(" ").append(i2 + 1).append(" ").append(v + 1).append("\n");
            }

            for (Integer i : adj[v]) {
                adj[i].remove(v);
                if (!explored[i] && !route.contains(i)) {
                    dfs3(i);
                }
            }
        }

        void createRoute() {
            int v1 = i2, v2 = i1, prev1 = -1, prev2 = -1;
            while (adj[v1].size() <= 2) {
                route.add(v1);
                int temp = v1;
                Iterator<Integer> it = adj[v1].iterator();
                do {
                    v1 = it.next();
                } while (v1 == prev1);
                prev1 = temp;
            }
            while (adj[v2].size() <= 2) {
                route.add(v2);
                int temp = v2;
                Iterator<Integer> it = adj[v2].iterator();
                do {
                    v2 = it.next();
                } while (v2 == prev2);
                prev2 = temp;
            }
            route.add(v2);
        }

        StringBuilder solve() {
            dfs(0, 0, dist2);
            i2 = i1;
            max = 0;
            Arrays.fill(explored, false);
            dfs(i2, 0, dist2);
            int t = i1;
            Arrays.fill(explored, false);
            dfs(i1, 0, dist1);
            i1 = t;

            Arrays.fill(explored, false);
            dfs1(0);
            Arrays.fill(explored, false);
            if (i2 != 0 && i1 != 0 && adj[0].size() == 1) {
                createRoute();
                dfs3(0);
            }
            Arrays.fill(explored, false);
            dfs2(i1);

            StringBuilder opt = new StringBuilder();
            opt.append(ans).append("\n").append(temp);
            return opt;
        }
    }

    public static void main(String args[]) throws Exception {

        FastReader fr = new FastReader();
        int n = fr.nextInt();
        Graph g = new Graph(n);

        for (int i = 0; i < n - 1; i++)
            g.addEdge(fr.nextInt() - 1, fr.nextInt() - 1);

        System.out.print(g.solve());
    }
}