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:
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {0, -1, 0, 1};
    int[] dy = {1, 0, -1, 0};

    int n;
    List<List<Integer>> graph = new ArrayList<>();
    int[] d1;
    int[] d2;
    int[] indegree;
    void solve() throws IOException {
        n = nextInt();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        d1 = new int[n];
        d2 = new int[n];
        indegree = new int[n];
        for (int i = 0; i < n - 1; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            graph.get(u).add(v);
            graph.get(v).add(u);
            indegree[u]++;
            indegree[v]++;
        }

        int[] tmp = new int[n];
        dfs(0, -1, tmp, 0);
        int p1 = -1;
        int max = -1;
        for (int i = 0; i < n; i++) {
            if (max < tmp[i]) {
                max = tmp[i];
                p1 = i;
            }
        }
        dfs(p1, -1, d1, 0);
        int p2 = -1;
        max = -1;
        for (int i = 0; i < n; i++) {
            if (max < d1[i]) {
                max = d1[i];
                p2 = i;
            }
        }
        dfs(p2, -1, d2, 0);
        long res = 0;
        Deque<Integer> deck = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 1 && i != p1 && i != p2) {
                deck.addLast(i);
            }
        }

        List<Integer> as = new ArrayList<>();
        List<Integer> bs = new ArrayList<>();
        List<Integer> cs = new ArrayList<>();
        while (!deck.isEmpty()) {
            int cur = deck.removeFirst();
            if (d1[cur] > d2[cur]) {
                res += d1[cur];
                as.add(p1);
            }
            else {
                res += d2[cur];
                as.add(p2);
            }
            bs.add(cur);
            cs.add(cur);
            for (int nxt : graph.get(cur)) {
                indegree[nxt]--;
                if (indegree[nxt] == 1) {
                    deck.add(nxt);
                }
            }
        }

        deck.add(p1);
        deck.add(p2);
        int diameter = d2[p1];
        while (deck.size() > 1) {
            int cur = deck.peekFirst();
            res += diameter;
            diameter--;
            as.add(cur);
            int p = deck.removeLast();
            bs.add(p);
            cs.add(p);
            for (int nxt : graph.get(p)) {
                indegree[nxt]--;
                if (indegree[nxt] == 1) {
                    deck.addLast(nxt);
                }
            }
        }

        outln(res);
        for (int i = 0; i < as.size(); i++) {
            out((1 + as.get(i)) + " ");
            out((1 + bs.get(i)) + " ");
            out(cs.get(i) + 1);
            outln("");
        }
    }

    void dfs(int cur, int parent, int[] depth, int d) {
        depth[cur] = d;
        for (int nxt : graph.get(cur)) {
            if (parent == nxt) {
                continue;
            }
            dfs(nxt, cur, depth, 1 + d);
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}