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.*;

public class SPOJANDCC
{
	@SuppressWarnings("rawtypes")
	static InputReader in;
	static PrintWriter out;

	static void dfs(int u, int p)
	{
		for (int i : a[u])
		{
			if (i == p)
				continue;
			dis[i] = dis[u] + 1;
			tmp[i] = u;
			dfs(i, u);
		}
	}

	static ArrayList<Integer> a[];
	static int dis[], tmp[];
	static int depth[][], parent[][];

	@SuppressWarnings("unchecked")
	static void solve()
	{
		int mx = (int) 2e5 + 10;
		dis = new int[mx];
		int n = in.ni();
		a = new ArrayList[mx];
		for (int i = 0; i < mx; i++)
			a[i] = new ArrayList<Integer>();
		for (int i = 1; i < n; i++)
		{
			int x = in.ni(), y = in.ni();
			a[x].add(y);
			a[y].add(x);
		}
		tmp = new int[mx];
		dfs(1, 0);
		int ind = 0;
		int mm = 0;
		for (int i = 1; i <= n; i++)
			if (dis[i] >= mm)
			{
				mm = dis[i];
				ind = i;
			}
		depth = new int[mx][2];
		parent = new int[mx][2];
		Arrays.fill(dis, 0);
		Arrays.fill(tmp, 0);
		dfs(ind, 0);
		for (int i = 1; i <= n; i++)
		{
			depth[i][0] = dis[i];
			parent[i][0] = tmp[i];
		}
		int ind2 = 0;
		mm = 0;
		for (int i = 1; i <= n; i++)
			if (dis[i] >= mm)
			{
				mm = dis[i];
				ind2 = i;
			}
		Arrays.fill(dis, 0);
		Arrays.fill(tmp, 0);
		dfs(ind2, 0);
		for (int i = 1; i <= n; i++)
		{
			depth[i][1] = dis[i];
			parent[i][1] = tmp[i];
		}
		long ans = 0;
		boolean u[] = new boolean[n + 1];
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 1; i <= n; i++)
			if (a[i].size() == 1 && i != ind && i != ind2)
			{
				q.add(i);
				u[i] = true;
			}
		ArrayList<String> l = new ArrayList<String>();
		int kk[] = new int[n + 1];
		for (int i = 1; i <= n; i++)
			kk[i] = a[i].size();
		while (!q.isEmpty())
		{
			int p = q.poll();
			if (depth[p][0] > depth[p][1])
				l.add(p + " " + ind + " " + p);
			else
				l.add(p + " " + ind2 + " " + p);
			for (int i : a[p])
			{
				kk[i]--;
				if (kk[i]==1 && !u[i])
				{
					q.add(i);
					u[i] = true;
				}
			}
			//debug(p);
			ans += Math.max(depth[p][0], depth[p][1]);
		}
		q.add(ind);
		//debug(ind,ind2);
		u[ind] = true;
		while (!q.isEmpty())
		{
			int p = q.poll();
			l.add(p + " " + ind2 + " " + p);
			for (int i : a[p])
			{
				kk[i]--;
				if (kk[i] == 1 && !u[i])
				{
					kk[i]--;
					q.add(i);
					u[i] = true;
				}
			}
			ans += depth[p][1];
		}
		out.println(ans);
		for (String i : l)
			out.println(i);
	}

	@SuppressWarnings("rawtypes")
	static void soln()
	{
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args)
	{
		new Thread(null, new Runnable()
		{
			public void run()
			{
				try
				{
					soln();
				} catch (Exception e)
				{
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	static class InputReader<SpaceCharFilter>
	{

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int snext()
		{
			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 = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

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

		public long[] nextLongArray(int n)
		{
			long a[] = new long[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = nl();
			}
			return a;
		}

		public String readString()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine()
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}

	}
}