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.util.* ;
import java.text.* ;
import java.math.* ;
import static java.lang.Math.min ;
import static java.lang.Math.max ;
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		// Solver Machine = new Solver() ;
		// Machine.Solve() ;
		// Machine.Finish() ;
		new Thread(null,new Runnable(){
			public void run(){
				Solver Machine = new Solver() ;
				try{
					Machine.Solve() ;
					Machine.Finish() ;
				}catch(Exception e){
					e.printStackTrace() ;
					System.out.flush() ;
					System.exit(-1) ;
				}catch(Error e){
					e.printStackTrace() ;
					System.out.flush() ;
					System.exit(-1) ;
				}
			}
		},"Solver",1l<<27).start() ;
	}
}
class Mod{
	static long mod=1000000007 ;
	static long d(long a,long b){ return (a*MI(b))%mod ; }
	static long m(long a,long b){ return (a*b)%mod ; }
	static private long MI(long a){ return pow(a,mod-2) ; }
	static long pow(long a,long b){
		if(b<0) return pow(MI(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%mod ; 
			val = (val*val)%mod ; 
			b/=2 ;
		}
		return ans ;
	}	
}
class pair implements Comparable<pair>{
	int x ; int y ; 
	pair(int x,int y){ this.x=x ; this.y=y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
class Solver{
	Reader ip = new Reader(System.in) ;	  
	PrintWriter op = new PrintWriter(System.out) ;
	mylist adj[] ;
	int dep[],dep2[],par[],hit[] ;
	long score=0 ;
	ArrayList<pair> res ;
	int deep,deep2 ;
	public void Solve() throws IOException{
		int n = ip.i() ;
		adj = new mylist[n+1] ;
		dep = new int[n+1] ;
		dep2 = new int[n+1] ;
		par = new int[n+1] ;
		hit = new int[n+1] ;
		res = new ArrayList<pair>() ;
		for(int i=1 ; i<=n ; i++) adj[i] = new mylist() ;
		for(int i=1 ; i<n ; i++){
			int u = ip.i() ;
			int v = ip.i() ;
			adj[u].add(v) ;
			adj[v].add(u) ;
		} 
		dep[0]=-1 ; dep2[0]=-1 ;
		par[1]=0 ;
		dfs(1) ;
		deep = -1 ;
		int mdep = Integer.MIN_VALUE;
		for(int i=1 ; i<=n ; i++){
			if(dep[i]>mdep){
				mdep = dep[i] ;
				deep=i ;
			}
		}
		par[deep]=0 ;
		dfs(deep) ;
		deep2 = -1 ;
		mdep = Integer.MIN_VALUE ;
		for(int i=1 ; i<=n ; i++){
			if(dep[i]>mdep){
				mdep = dep[i] ;
				deep2=i ;
			}
		}
		mylist dia = new mylist() ;
		int itr = deep2 ;
		while(itr!=deep){
			dia.add(itr) ;
			itr = par[itr] ;
		}
		dia.add(deep) ;
		for(int elem : dia) hit[elem]=1 ;
		dfs2(deep2,0) ;
		dfs3(deep,0) ;
		long d = (dia.size()-1) ;
		score+=((d*(d+1))/2) ;
		for(int elem : dia) res.add(new pair(deep,elem)) ;
		res.remove(res.size()-1) ;
		pln(score) ;
		for(pair elem : res) pln(elem.x+" "+elem.y+" "+elem.y) ;	
	}
	void dfs3(int nd,int par){
		for(int chd : adj[nd])
			if(chd!=par)
				dfs3(chd,nd) ;
		if(hit[nd]==0){
			if(dep[nd]<dep2[nd]){
				res.add(new pair(deep2,nd)) ;
				score+=dep2[nd] ;
			}else{
				res.add(new pair(deep,nd)) ;
				score+=dep[nd] ;
			}
		}
	}
	void dfs(int nd){
		dep[nd] = dep[par[nd]]+1 ;
		for(int chd : adj[nd])
			if(chd!=par[nd]){
				par[chd] = nd ;
				dfs(chd) ;
			}
	}
	void dfs2(int nd,int par){
		dep2[nd] = dep2[par]+1 ;
		for(int chd : adj[nd])
			if(chd!=par)
				dfs2(chd,nd) ;
	}
	void Finish(){
		op.flush();
		op.close();
	}
	void p(Object o){
		op.print(o) ;
	}
	void pln(Object o){
		op.println(o) ;
	}		
}
class mylist extends ArrayList<Integer>{}
class myset extends TreeSet<Integer>{}
class mystack extends Stack<Integer>{}
class mymap extends TreeMap<Long,Integer>{}
class Reader{
	BufferedReader reader;
	StringTokenizer tokenizer;
	Reader(InputStream input) {
		reader = new BufferedReader(
					new InputStreamReader(input) );
		tokenizer = new StringTokenizer("") ;
	}
	String s() throws IOException {
		while (!tokenizer.hasMoreTokens()){
			tokenizer = new StringTokenizer(
			reader.readLine()) ;
		}
		return tokenizer.nextToken();
	}
	int i() throws IOException {
		return Integer.parseInt(s()) ;
	}
	long l() throws IOException{
		return Long.parseLong(s()) ;
	}
	double d() throws IOException {
		return Double.parseDouble(s()) ;
	}
}