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:
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;

public class A
{
	
	InputStream in;
	PrintWriter out;

	void solve() 
	{
		int n=ni();
		init_g(n);
		for (int i=0;i<n-1;i++)
		{
			int u=ni()-1;
			int v=ni()-1;
			g[u].add(v);
			g[v].add(u);
		}
		dfs1(0,0,0);
		dv1=maxidx;
		max=0;
		dfs1(maxidx,maxidx,0);
		dv2=maxidx;
		dfs(dv1,dv1,dv2);
		dfs2(dv1,dv1,0,dv1);
		dfs2(dv2,dv2,0,dv2);
		long ans=0;
		diameter[dv1]=true;diameter[dv2]=true;
		//tr(dv1,dv2);
		for (int i=0;i<n;i++)
			if (!diameter[i])
				ans+=node[i][0];
		ans+=dfs5(dv1,dv1,0);
		out.println(ans);
		//tr(node);
		//tr(dv1,dv2);
		dfs3(dv1,dv1);
		dfs4(dv1,dv1,dv1);
	}
	
	int node[][];
	boolean diameter[];
	
	int max,maxidx;
	void dfs1(int u,int p,int l)
	{
		for (int v:g[u])
		{
			if (v!=p)
				dfs1(v,u,l+1);
		}
		if (l>max)
		{
			max=l;
			maxidx=u;
		}
	}
	
	int dv1,dv2;
	
	boolean dfs(int u,int p,int d)
	{
		if (u==d)
		{
			diameter[u]=true;
			return true;
		}
		for (int v:g[u])
		{
			if (v!=p)
				diameter[u]|=dfs(v,u,d);
		}
		return diameter[u];
	}
	
	void dfs3(int u,int p)
	{
		for (int v:g[u])
		{
			if (v!=p)
				dfs3(v,u);
		}
		if (!diameter[u])
			out.println(node[u][1]+1+" "+(u+1)+" "+(u+1));
	}
	
	void dfs4(int u,int p,int d)
	{
		for (int v:g[u])
		{
			if (v!=p)
				dfs4(v,u,d);
		}
		if (diameter[u]&&u!=d)
			out.println(d+1+" "+(u+1)+" "+(u+1));
	}
	
	long dfs5(int u,int p,int l)
	{
		long ans=0;
		for (int v:g[u])
		{
			if (v!=p)
				ans+=dfs5(v,u,l+1);
		}
		if (diameter[u])
			ans+=l;
		return ans;
	}
	
	void dfs2(int u,int p,int l,int d)
	{
		if (node[u][0]<l)
		{
			node[u][0]=l;
			node[u][1]=d;
		}
		for (int v:g[u])
		{
			if (v!=p)
				dfs2(v,u,l+1,d);
		}
	}
	
	ArrayList<Integer> g[];
	void init_g(int n)
	{
		g=new ArrayList[n];
		node=new int[n][2];
		diameter=new boolean[n];
		for (int i=0;i<n;i++)
		{
			g[i]=new ArrayList<Integer>();
		}
	}
	
	int MAX = (int)1e5;
	long factorial[];
	void findfactorial() 
	{
		factorial = new long[MAX + 1];
		factorial[0] = 1;
		for (int i = 1; i < MAX + 1; i++) 
		{
			factorial[i] = mul(i,factorial[i - 1]);
		}
	}
	
	long mod=(long)1e9+7;
	long add(long a,long b)
	{
		long x=(a+b);
		while(x>=mod) x-=mod;
		return x;
		
	}
	
	
	long sub(long a,long b)
	{
		long x=(a-b);
		while(x<0) x+=mod;
		return x;
		
	}
	
	
	long mul(long a,long b)
	{
		a%=mod;
		b%=mod;
		long x=(a*b);
		return x%mod;
		
	}
	
	int max(int a,int b)
	{
		if(a>b)
			return a;
		else
			return b;
	}
	
	int min(int a,int b)
	{
		if(a>b)
			return b;
		else 
			return a;
	}
	
	long max(long a,long b)
	{
		if(a>b)
			return a;
		else
			return b;
		
	}
	
	
	long min(long a,long b)
	{
		if(a>b)
			return b;
		else 
			return a;
		
	}
		
	void run() throws Exception 
	{
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		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 = in.read(inbuf);
			}
			catch (IOException e) 
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) 
	{
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() 
	{
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(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 (!(inSpaceChar(b))) 
		{ // when nextLine, (inSpaceChar(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 && !(inSpaceChar(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 boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}