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:
//package practice.pset1;

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

public class E35F {

    static int[][] adj;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int n = sc.nextInt();
        int[] from = new int[n-1];
        int[] to = new int[n-1];
        int[] degree = new int[n];
        for (int i = 0; i < n - 1; i++) {
            from[i] = sc.nextInt() - 1;
            to[i] = sc.nextInt() - 1;
            degree[from[i]]++;
            degree[to[i]]++;
        }
        adj = packU(n, from, to);

        // treediameter a-b
        int[] q = new int[n];
        int[] vis = new int[n];
        int vid = 1;
        q[0] = 0;
        vis[0] = vid;

        int a = 0;
        for (int st = 0, en = 1; st < en;) {
            int u = q[st++];
            a = u;
            for(int v: adj[u])
                if(vis[v] != vid){
                    vis[v] = vid;
                    q[en++] = v;
                }
        }

        int b = a;
        q[0] = a;
        vid++;
        vis[a] = vid;
        for(int st = 0, en = 1; st<en;){
            int u = q[st++];
            b = u;
            for (int v: adj[u]) {
                if(vis[v] != vid){
                    vis[v] = vid;
                    q[en++] = v;
                }
            }
        }

        // d1
        int[] distA = new int[n];
        int[] para = new int[n];
        long cuma = 0;
        vid++;
        para[a] = -1;
        q[0] = a;
        vis[a] = vid;
        for(int st = 0, en = 1; st<en;){
            int u = q[st++];
            cuma += distA[u];
            for (int v: adj[u]) {
                if(vis[v] != vid){
                    vis[v] = vid;
                    q[en++] = v;
                    distA[v] = distA[u] + 1;
                    para[v] = u;
                }
            }
        }

        // d2
        int[] distB = new int[n];
        int[] parb = new int[n];
        long cumb = 0;
        q[0] = b;
        parb[b] = -1;
        vid++;
        vis[b] = vid;
        for(int st = 0, en = 1; st<en;){
            int u = q[st++];
            cumb += distB[u];
            for (int v: adj[u]) {
                if(vis[v] != vid){
                    vis[v] = vid;
                    q[en++] = v;
                    distB[v] = distB[u] + 1;
                    parb[v] = u;
                }
            }
        }

        boolean onDiameter[] = new boolean[n];
        int cur = b;
        while(cur != -1){
            onDiameter[cur] = true;
            cur = para[cur];
        }


        int st = 0, en = 0;
        for (int i = 0; i < degree.length; i++) {
            if(degree[i] == 1 && !onDiameter[i])
                q[en++] = i;
        }

        long ans = 0;
        StringBuilder sb = new StringBuilder("");
        while(st < en){
            int rem = q[st++];
            if(distA[rem] > distB[rem]){
                ans += distA[rem];
                sb.append(a+1 + " " + (rem+1) + " " + (rem+1) + "\n");
                if(para[rem] != -1 && --degree[para[rem]] == 1)
                    q[en++] = para[rem];
            }else // b
            {
                ans += distB[rem];
                sb.append(b+1 + " " + (rem+1) + " " + (rem+1) + "\n");
                if(parb[rem] != -1 && --degree[parb[rem]] == 1)
                    q[en++] = parb[rem];
            }
        }

        cur = b;
        while(cur != a)
        {
            ans += distA[cur];
            sb.append(a+1 + " " + (cur+1) + " " + (cur+1) + "\n");
            cur = para[cur];
        }

        pw.println(ans);
        pw.print(sb);

        pw.flush();
        pw.close();
    }



    static int[][] packD(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from) if(f != -1) p[f]++;
        for (int i = 0; i < n; i++) g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) if(from[i] != -1) {g[from[i]][--p[from[i]]] = to[i];}
        return g;
    }

    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }

    static 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;
        }
    }

    static class Scanner
    {
        StringTokenizer st; BufferedReader br;
        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
        public Scanner(String s) throws FileNotFoundException {	br = new BufferedReader(new FileReader(new File(s)));}
        public String next() throws IOException {while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
        public int nextInt() throws IOException {return Integer.parseInt(next());}
        public long nextLong() throws IOException {return Long.parseLong(next());}
        public String nextLine() throws IOException {return br.readLine();}
        public boolean ready() throws IOException {return br.ready();}
    }
}