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

public class Main {

	BufferedReader in;
	StringTokenizer str = null;
	PrintWriter out;
	
	private String next() throws Exception{
		while (str == null || !str.hasMoreElements())
			str = new StringTokenizer(in.readLine());
		return str.nextToken();
	}
	
	private int nextInt() throws Exception{
		return Integer.parseInt(next());
	}
	
	private long nextLong() throws Exception{
		return Long.parseLong(next());
	}
	
	private double nextDouble() throws Exception{
		return Double.parseDouble(next());
	}

	private final static int oo = Integer.MAX_VALUE / 2;

	int n;
	List<Integer> []g;
	boolean []inDiameter;
	
	public void run() throws Exception{
		in =  new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		n = nextInt();
		g = new LinkedList[n];
		for(int i = 0; i < n; ++i) {
			g[i] = new LinkedList<>();
		}	
		for(int i = 0; i < n - 1; ++i) {
			int v = nextInt() - 1, u = nextInt() - 1;
			g[v].add(u);
			g[u].add(v);
		}

		inDiameter = new boolean[n];
		int []vert = bfs(0, 0);
		// System.out.println("diameter leaves = " + Arrays.toString(vert));
		// System.out.println("in diameter = " + Arrays.toString(inDiameter));
		int s = vert[0], f = vert[1];
		int []d1 = bfs(s), d2 = bfs(f);
		// System.out.println("from " + s + " = " + Arrays.toString(d1));
		// System.out.println("from " + f + " = " + Arrays.toString(d2));
		
		

		PriorityQueue<P> pq = new PriorityQueue<>();
		for(int i = 0; i < n; ++i) {
			if (inDiameter[i]) {
				continue;
			}	
			if (d1[i] >= d2[i]) {
				pq.add(new P(s, i, d1[i]));
			} else {
				pq.add(new P(f, i, d2[i]));
			}
		}

		List<int[]> ans = new LinkedList<>();
		long ret = 0;
		while(pq.size() > 0) {
			P cur = pq.poll();
			ans.add(new int[]{cur.v + 1, cur.from + 1, cur.v + 1});
			ret += cur.d;
		}	
		int cur = f;
		while(cur != s) {
			ret += d1[cur];
			ans.add(new int[]{s + 1, cur + 1, cur + 1});
			cur = from[cur];
		}
		out.println(ret);
		for(int []vs : ans) {
			for(int j : vs) {
				out.print(j + " ");
			}
			out.println();
		}
		out.close();
	}

	int []d, from;
	Queue<Integer> q;
	private int[] bfs(int s, int t) {

		d = new int[n];
		Arrays.fill(d, oo);
		from = new int[n];
		Arrays.fill(from, -1);

		q = new LinkedList<>();	

		d[s] = 0;
		q.add(s);
		while(q.size() > 0) {
			int v = q.poll();
			for(int i : g[v]) {
				if (d[i] > d[v] + 1) {
					from[i] = v;
					d[i] = d[v] + 1;
					q.add(i);
				}
			}
		}

		int maxV = -1;
		for(int i = 0; i < n; ++i) {
			if (maxV == -1 || d[maxV] < d[i]) {
				maxV = i;
			}
		}
		if (t == 0) {
			return bfs(maxV, 1);
		} else {
			int cur = maxV;	
			while(cur != -1) {
				inDiameter[cur] = true;
				cur = from[cur];
			}
			return new int[]{s, maxV};
		}
	}

	private int[] bfs(int v) {
		int []d = new int[n];
		Arrays.fill(d, oo);
		d[v] = 0;
		q = new LinkedList<>();
		q.add(v);

		while(q.size() > 0) {
			int c = q.poll();
			for(int i : g[c]) {
				if (d[i] > d[c] + 1) {
					d[i] = d[c] + 1;
					q.add(i);
				}
			}
		}
		return d;
	}

	static class P implements Comparable<P> {
		int from, v, d;
		public P(int from, int v, int d) {
			this.from = from;
			this.v = v;
			this.d = d;
		}

		public int compareTo(P other) {
			if (this.d != other.d) {
				return other.d - this.d;
			}
			return this.v - other.v;
		}
	}
		
	public static void main(String[] args) throws Exception{
		new Main().run();
	}
}