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:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF911F extends PrintWriter {
	CF911F() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF911F o = new CF911F(); o.main(); o.flush();
	}

	int[] oo, oj; int __ = 1;
	int link(int o, int j) {
		oo[__] = o; oj[__] = j;
		return __++;
	}
	int[] ae, pp; boolean[] visited;
	int[] aa, bb; int cnt; long ans = 0;
	void init(int n) {
		int m = n - 1;
		oo = new int[1 + m * 2]; oj = new int[1 + m * 2];
		ae = new int[n]; pp = new int[n];
		visited = new boolean[n];
		aa = new int[n - 1]; bb = new int[n - 1];
	}
	int d_, i_;
	void dfs(int p, int i, int d) {
		if (d_ < d) {
			d_ = d; i_ = i;
		}
		pp[i] = p;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p)
				dfs(i, j, d + 1);
		}
	}
	void dfs_(int i, int d, int b) {
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (!visited[j]) {
				visited[j] = true;
				ans += d + 1;
				dfs_(j, d + 1, b);
				aa[cnt] = j; bb[cnt] = b; cnt++;
			}
		}
	}
	void main() {
		int n = sc.nextInt();
		init(n);
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ae[i] = link(ae[i], j);
			ae[j] = link(ae[j], i);
		}
		dfs(-1, 0, 0);
		d_ = 0;
		int j_ = i_;
		dfs(-1, i_, 0);
		ans = (long) d_ * (d_ + 1) / 2;
		for (int i = i_; i != -1; i = pp[i])
			visited[i] = true;
		for (int i = i_, d = 0; i != -1; i = pp[i], d++)
			dfs_(i, Math.max(d, d_ - d), d >= d_ - d ? i_ : j_);
		for (int i = i_; i != j_; i = pp[i]) {
			aa[cnt] = i; bb[cnt] = j_; cnt++;
		}
		println(ans);
		for (int h = 0; h < cnt; h++)
			println((aa[h] + 1) + " " + (bb[h] + 1) + " " + (aa[h] + 1));
	}
}