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

public class Main implements Runnable {

    public static void main(String[] args) {
        new Thread(null, new Main(), "_cf", 1 << 28).start();
    }

    private static int n;
    private static Set<Integer>[] graph;
    private static long ans = 0L;
    private static String deletions = "";
    private int[] maxDistance;
    PriorityQueue<Pair> set = new PriorityQueue<>(new Comparator<Pair>() {
        @Override
        public int compare(Pair o1, Pair o2) {
            if (maxDistance[o2.snd] != maxDistance[o1.snd]) {
                return (maxDistance[o2.snd] - maxDistance[o1.snd]);
            }
            return o1.snd - o2.snd;
        }
    });
    private int[] a;
    private int[] b;
    private static JoltyScanner scanner = new JoltyScanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public void run() {
        n = scanner.nextInt();
        graph = new Set[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new HashSet<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            graph[u].add(v);
            graph[v].add(u);
        }

        solve();
        out.println(ans);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            sb.append(a[i] + " " + b[i] + " " + b[i] + "\n");
        }
        out.println(sb);
//        if (n == 200000) {
//            out.println("piska4");
//            return;
//        }
        out.close();
    }

    private void solve() {
        FurthestVertexFinder furthestVertexFinder = new FurthestVertexFinder(graph);
        Integer d1 = furthestVertexFinder.find(0);
//        out.println("d1 = " + (d1 + 1));
        Integer d2 = furthestVertexFinder.find(d1);
//        out.println("d2 = " + (d2 + 1));

        Set<Integer> diameter = new PathFinder(graph).findPath(d1, d2);
//        out.println(diameter.toString());


        int[] distanseToD1 = new int[n];
        findDistances(d1, 0, distanseToD1, d1);
        int[] distanseToD2 = new int[n];
        findDistances(d2, 0, distanseToD2, d2);
        maxDistance = new int[n];


        for (int v = 0; v < n; v++) {
            if (!diameter.contains(v)) {
                if (distanseToD1[v] > distanseToD2[v]) {
                    maxDistance[v] = distanseToD1[v];
                    set.add(new Pair(d1, v));
                } else {
                    maxDistance[v] = distanseToD2[v];
                    set.add(new Pair(d2, v));
                }
            }
        }

        a = new int[n - 1];
        b = new int[n - 1];
        int i = 0;

        while (!set.isEmpty()) {
            Pair pair = set.poll();
            ans += maxDistance[pair.snd];
            a[i] = pair.fst + 1;
            b[i] = pair.snd + 1;
            i++;
//            deletions += "" + (pair.fst + 1) + " " + (pair.snd + 1) + " " + (pair.snd + 1) + "\n";
        }


        TreeSet<Integer> setForDiametr = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return (distanseToD1[o2] - distanseToD1[o1]);
            }
        });

        diameter.remove(d1);
        setForDiametr.addAll(diameter);
//        out.println(setForDiametr.toString());
        while (!setForDiametr.isEmpty()) {
            int v = setForDiametr.pollFirst();
            ans += distanseToD1[v];
            a[i] = (d1 + 1);
            b[i] = (v + 1);
            i++;
//            deletions += "" + (d1 + 1) + " " + (v + 1) + " " + (v + 1) + "\n";
        }



    }

    private void findDistances(int v, int distance, int[] distanseTo, int previous) {
        distanseTo[v] = distance;
        for (Integer u : graph[v]) {
            if (u != previous) {
                findDistances(u, distance + 1, distanseTo, v);

            }
        }
    }


    private static class PathFinder {
        private Set<Integer>[] graph;
        private Set<Integer> path = new HashSet<>();
        private boolean pathFound = false;
        private int theEnd;

        public PathFinder(Set<Integer>[] graph) {
            this.graph = graph;
        }

        public Set<Integer> findPath(int start, int end) {
            path.clear();
            theEnd = end;
            pathFound = false;
            findPathDFS(start, start);
            return path;
        }

        private void findPathDFS(int v, int previous) {
            if (v == theEnd) {
                pathFound = true;
                path.add(v);
                return;
            }
            path.add(v);
            for (Integer u : graph[v]) {
                if (u != previous) {
                    findPathDFS(u, v);
                    if (pathFound) {
                        return;
                    }
                }


            }
            path.remove(v);
        }

    }

    private static class FurthestVertexFinder {
        private Set<Integer>[] graph;
        private Integer maxDistance;
        private Integer furthestVertex;

        public FurthestVertexFinder(Set<Integer>[] graph) {
            this.graph = graph;
        }

        public Integer find(int v) {
            maxDistance = 0;
            furthestVertex = v;
            findFurthestVertex(v, 0, v);
            return furthestVertex;
        }

        private void findFurthestVertex(int v, int distance, int previous) {
            if (distance >= maxDistance) {
                maxDistance = distance;
                furthestVertex = v;
            }
            for (Integer u :
                    graph[v]) {
                if (u != previous) {
                    findFurthestVertex(u, distance + 1, v);
                }
            }
        }
    }

    private static class Pair {
        public int fst;
        public int snd;

        public Pair(int fst, int snd) {
            this.fst = fst;
            this.snd = snd;
        }

        @Override
        public String toString() {
            return "[" + fst + ", " + snd + "]";
        }
    }

    static class JoltyScanner {
        public static final int BUFFER_SIZE = 1 << 16;
        public static final char NULL_CHAR = (char) -1;
        byte[] buffer = new byte[BUFFER_SIZE];
        int bufferIdx = 0, size = 0;
        char c = NULL_CHAR;
        BufferedInputStream in;

        public JoltyScanner(InputStream in) {
            this.in = new BufferedInputStream(in, BUFFER_SIZE);
            c = nextChar();
        }

        public int nextInt() {
            while (c < '0' || c > '9')
                c = nextChar();
            int res = 0;
            while (c >= '0' && c <= '9') {
                res = (res << 3) + (res << 1) + c - '0';
                c = nextChar();
            }
            return res;
        }

        public char nextChar() {
            while (bufferIdx == size) {
                try {
                    size = in.read(buffer);
                } catch (Exception e) {
                    return NULL_CHAR;
                }
                bufferIdx = 0;
            }
            return (char) buffer[bufferIdx++];
        }
    }


}