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

public class Codeforces {

    private static void addVertex(int vertex, int u, int v, int[] distU, int[] distV, PrintWriter writer) {
        int diameterV = u;
        if (distV[vertex] > distU[vertex])
            diameterV = v;
        writer.printf("%d %d %d %n", diameterV + 1, vertex +1, vertex+1);
    }

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

        Scanner scan = new Scanner(System.in);
        //Scanner scan = new Scanner(new File("test.txt"));

        int n = scan.nextInt();

        List<List<Integer>> tree = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int a = scan.nextInt() - 1;
            int b = scan.nextInt() - 1;
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        List<Integer> queue = new ArrayList<>();
        int[] parents = new int[n];
        bfs(tree, 0, queue, new int[n]);
        int u = queue.get(queue.size()-1);
        queue.clear();
        int[] distU = bfs(tree, u, queue, new int[n]);
        int v = queue.get(queue.size()-1);
        int[] distV = bfs(tree, v, new ArrayList<>(), parents);

        boolean[] onUVpath = new boolean[n];
        for (int i = 0; i < n; i++)
            onUVpath[i] = false;

        int curNode = u;
        onUVpath[u] = true;
        while (curNode != v) {
            curNode = parents[curNode];
            onUVpath[curNode] = true;
        }

        long output = 0;

        for (int i = 0; i < n; i++)
            if (onUVpath[i])
                output += distV[i];
            else
                output += Math.max(distU[i], distV[i]);

        PrintWriter writer = new PrintWriter(System.out);
        writer.println(output);
        //System.out.println(output);

        for (int i = n-1; i>=0; i--) {
            if (!onUVpath[queue.get(i)]) {
                addVertex(queue.get(i), u, v, distU, distV, writer);
            }
        }

        for (int i = 0; i < n; i++)
            distU[i] = 0;
        curNode = u;
        while (curNode != v) {
            addVertex(curNode, u, v, distU, distV, writer);
            curNode = parents[curNode];
        }
        writer.flush();
    }

    private static int[] bfs(List<List<Integer>> tree, int start, List<Integer> queue, int[] parents) {

        int[] distances = new int[tree.size()];
        boolean[] visited = new boolean[tree.size()];

        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        queue.add(start);
        visited[start] = true;
        parents[start] = 0;

        while (!q.isEmpty()) {
            int current = q.poll();
            int distance = distances[current] + 1;

            List<Integer> neighbors = tree.get(current);

            for (Integer neig:neighbors) {
                if (!visited[neig]) {
                    distances[neig] = distance;
                    parents[neig] = current;
                    q.add(neig);
                    queue.add(neig);
                    visited[neig] = true;
                }
            }
        }

        return distances;
    }
    /*public class Heap {
        public Heap() {

        }

        public void addElement(int x) {

        }
    }*/

    public static class Scanner implements Closeable {
        private BufferedReader br;
        private StringTokenizer tok;

        public Scanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        private void getLine() {
            try {
                while (!hasNext()) {
                    tok = new StringTokenizer(br.readLine());
                }
            } catch (IOException e) { /* ignore */
            }
        }

        private boolean hasNext() {
            return tok != null && tok.hasMoreTokens();
        }

        public String next() {
            getLine();
            return tok.nextToken();
        }

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

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

        public void close() {
            try {
                br.close();
            } catch (IOException e) { /* ignore */
            }
        }
    }
}