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.lang.*;
import java.lang.reflect.Array;
import java.io.*;
import java.math.*;
import java.text.DecimalFormat;
public class Prac{     
    static class InputReader { 
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        public InputReader(InputStream st) {
            this.stream = st;
        } 
        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } 
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
            c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public int[] nia(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public String rs() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                    c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        } 
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        } 
    }
    static PrintWriter w = new PrintWriter(System.out);
    static long mod=998244353L,mod1=1000000007;
    public static class Key {
 
    private final int x;
    private final int y;
 
    public Key(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Key)) return false;
        Key key = (Key) o;
        return x == key.x && y == key.y;
    }
 
    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
 
}
    static class Pair{
        int x,y,z,l;
        public Pair(int x,int y,int z,int l){
            this.x=x;
            this.y=y;
            this.z=z;
            this.l=l;
        }
    }
    static TreeSet<Integer> arr[];
    static Pair fin;
    static int n,max=-1,max1=-1;
    static long length=0,length1=0;
    static ArrayList<Pair> ans=new ArrayList<>();
    static Map<Integer,Pair> ans1=new HashMap<>();
    static void dfs1(int root,int p,int len){
        for(int j:arr[root]){
            if(j!=p){
                dfs1(j,root,len+1);
            }
        }
        if(!st.contains(root)){
            ans.add(new Pair(max,root,root,len));
            //length+=(long)len;
        }
//        if(root==max1){
//            fin=new Pair(max,max1,max1,len);
//        }
        
    }
    static void dfs2(int root,int p,int len){
        for(int j:arr[root]){
            if(j!=p){
                dfs2(j,root,len+1);
            }
        }
        if(!st.contains(root)){
            ans1.put(root,new Pair(max1,root,root,len));
            //length1+=(long)len;
        }
        
    }
    static Set<Integer> st=new LinkedHashSet<>();
    static boolean f=false;
    static boolean path(int i,int p){
        if(i==max1){
            //f=true;
            st.add(i);
            return true;
        }
        st.add(i);
        for(int j:arr[i]){
            if(j!=p){
                if(path(j,i))return true;
            }
        }
        st.remove(i);
        return false;
    }
    public static void main (String[] args)throws IOException{
        InputReader sc=new InputReader(System.in);
        n=sc.ni();
        arr=new TreeSet[n+1];
        for(int i=0;i<=n;i++){
            arr[i]=new TreeSet<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.ni(),v=sc.ni();
            arr[u].add(v);arr[v].add(u);
        }
        Queue<Integer> q=new LinkedList<>();
        boolean v[]=new boolean[n+1];
        q.add(1);
        while(!q.isEmpty()){
            int s=q.size();
            while(s-->0){
                int x=q.poll();
                v[x]=true;
                max=x;
                for(int j:arr[x]){
                    if(!v[j])q.add(j);
                }
            }
        }
        q.clear();
        q.add(max);
        Arrays.fill(v,false);
        while(!q.isEmpty()){
            int s=q.size();
            while(s-->0){
                int x=q.poll();
                v[x]=true;
                max1=x;
                for(int j:arr[x]){
                    if(!v[j])q.add(j);
                }
            }
        }
        //st.add(max);
        path(max,max);
        
        dfs1(max,max,0);
        dfs2(max1,max1,0);
        ArrayList<Pair> res=new ArrayList<>();
        long len=0;
        Set<Integer> rem=new HashSet<>();
        int i=0,j=0;
        while(i<ans.size()){
            Pair p1=ans.get(i);
            Pair p2=ans1.get(p1.y);
            if(p1.l>=p2.l){
                res.add(p1);
                len+=(long)p1.l;
            }
            else{
                res.add(p2);
                len+=(long)p2.l;
            }
            i++;
        }
        st.remove(max1);
        long sum=st.size();
        for(int x:st){
            len+=sum;
            sum--;
            res.add(new Pair(max1,x,x,0));
        }
        w.println(len);
        for(Pair p:res){
            w.println(p.x+" "+p.y+" "+p.z);
        }
        w.close();
    }
}