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


public class Main {
    private static final int MAX = 200*1000 + 10;
    private static ArrayList<Integer> [] adj;
    private static int [] deg,depth,depth2 ;
    private static int n ;

    private static void preprocess(){
        adj = new ArrayList[n + 1];
        deg = new int[n + 1];
        depth = new int[n + 1];
        depth2 = new int[n + 1];
        for (int i = 1;i <= n;i++) adj[i] = new ArrayList<>();
        depth[0] = depth2[0] = -1;
    }

    private static int getFurthest(int u,int p,int [] depth) {
        depth[u] = depth[p] + 1;
        int ret = u;
        for (int v : adj[u]) if (v != p) {
            int t = getFurthest(v,u,depth);
            if (depth[t] > depth[ret])
                ret = t;
        }
        return ret;
    }
    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        n = io.getNextInt();
        preprocess();
        for (int i = 1;i < n;i++) {
            int a = io.getNextInt(),b = io.getNextInt();
            adj[a].add(b);
            adj[b].add(a);
            deg[a]++;
            deg[b]++;
        }

        int u = getFurthest(1,0,depth);
        int v = getFurthest(u,0,depth);
        getFurthest(v,0,depth2);
//        System.err.println(Arrays.toString(depth));
//        System.err.println(Arrays.toString(depth2));

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1;i <= n;i++) if (deg[i] == 1 && i != u && i != v) q.add(i);
        long ans = 0;
        ArrayList<quanta> out = new ArrayList<>(n-1);
        for (int ctr = 1,past = 0;ctr < n;ctr++){
            if (q.isEmpty()) {
                q.add(v);
                past = 1;
            }
            int t = q.poll(),o = u;
            if (past == 0 && depth[t] < depth2[t]) {
                o = v;
                ans += depth2[t];
            }
            else
                ans += depth[t];
            out.add(new quanta(o,t,t));
            for (int z : adj[t]) {
                deg[z]--;
                if (deg[z] == 1) q.add(z);
            }
        }
        io.println(ans);
        for (quanta o : out)
            io.println(o.a + " " + o.b + " " + o.c);
        io.close();
    }
}

class quanta{
    public int a,b,c;
    public quanta(int a,int b,int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}