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.util.*;
import java.io.*;
import java.math.*;
public class A{

    void solve(){
        int n=ni();
        graph=new ArrayList[n+1];
        for(int i=1;i<=n;i++) graph[i]=new ArrayList<>();
        for(int i=1;i<n;i++){
            int a=ni(); int b=ni();
            graph[a].add(b);
            graph[b].add(a);
        }
        dep=new int[n+1][3];
        dia=new boolean[n+1];
        parent=new int[n+1];
        dfs1(1,-1,0,1);
        mx=0;
        dfs1(e[1],-1,0,2);
        mx=0;
        dfs1(e[2],-1,0,3);
        int p=e[2];
        while(p!=-1){
            dia[p]=true;
            p=parent[p];
        }

        ArrayList<Integer> v[]=new ArrayList[n+1];
       for(int i=0;i<=n;i++) v[i]=new ArrayList<>();
        for(int i=1;i<=n;i++){
            v[dep[i][1]].add(i);

        }

        StringBuilder ans=new StringBuilder("");
        long total=0;
        for(int i=1;i<=n;i++){
            for(int u : v[i]){
                if(dia[u]) total+=dep[u][1];
                else total+=Math.max(dep[u][1],dep[u][2]);
            }
        }
        pw.println(total);
        for(int i=n;i>=1;i--){
            for(int u : v[i]){
                if(dia[u]){
                    int a=-1,b=-1,c=-1;
                    a=e[1];
                    b=c=u;
                    if(a==b) break;
                    ans.append(a+" "+b+" "+c+"\n");
                }
                else  {
                    int a=-1,b=-1,c=-1;
                    if(dep[u][1]>=dep[u][2]){
                        a=e[1];
                        b=c=u;
                        if(a==b) break;

                    }else {
                        a=e[2];
                        b=c=u;
                        if(a==b) break;

                    }
                    pw.println(a+" "+b+" "+c);
                }
            }
        }
        pw.println(ans);

    }

    boolean dia[];
    int dep[][];
    ArrayList<Integer> graph[];
    int e[]=new int[4];
    int mx=0;
    int parent[];
    void dfs1(int v,int pr,int cnt,int d){

        dep[v][d-1]=cnt;
        if(cnt>mx){
            mx=cnt;
            e[d]=v;
        }
        if(d==2){
            parent[v]=pr;
        }
        for(int u : graph[v]){
            if(u!=pr) dfs1(u,v,cnt+1,d);
        }

    }

    long M=(long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";
    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }

    public static void main(String[] args) throws Exception { new A().run(); }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }
}