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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class f implements Runnable {

	public static void main(String[] args) {
		new Thread(null, new f(), "Main", 1 << 28).start();
	}

	static class HLD {
		int[] size, in, out, rin, nxt, parent, depth;
		int t, n;
		ArrayList<Integer> adj[];

		void getSizes(int v, int p, int d) {
			size[v] = 1;
			depth[v] = d;
			parent[v] = p;
			for (int i = 0; i < adj[v].size(); i++) {
				int u = adj[v].get(i);
				if (p == u)
					continue;
				getSizes(u, v, d + 1);
				size[v] += size[u];
				if (size[u] > size[adj[v].get(0)]) {
					adj[v].set(i, adj[v].get(0));
					adj[v].set(0, u);
				}
			}
		}

		void eulerTree(int v, int p) {
			in[v] = t++;
			rin[in[v]] = v;
			for (int u : adj[v]) {
				if (u == p)
					continue;
				nxt[u] = (u == adj[v].get(0) ? nxt[v] : u);
				eulerTree(u, v);
			}
			out[v] = t;
		}

		HLD(ArrayList<Integer> adj[]) {
			this.adj = adj;
			n = adj.length;
			size = new int[n];
			in = new int[n];
			out = new int[n];
			rin = new int[n];
			nxt = new int[n];
			parent = new int[n];
			depth = new int[n];

			nxt[0] = -1;
			getSizes(0, -1, 0);
			eulerTree(0, -1);
		}

		boolean isAncestor(int u, int v) {
			return (in[v] >= in[u] && in[v] < out[u]);
		}

		int lca(int u, int v) {
			if (isAncestor(u, v))
				return u;
			if (isAncestor(v, u))
				return v;
			if (in[u] < in[v])
				return lca(u, parent[nxt[v]]);

			return lca(parent[nxt[u]], v);

		}
	}

	static ArrayList<Integer> adj[];
	
	
	public void run() {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		// BEGIN HERE
		try {

			int n = in.nextInt();
			int count[] = new int[n];
			adj = new ArrayList[n];
			for (int i = 0; i < n; i++)
				adj[i] = new ArrayList<>();

			for (int i = 0; i < n - 1; i++) {
				int u = in.nextInt() - 1;
				int v = in.nextInt() - 1;
				count[u]++;
				count[v]++;
				adj[u].add(v);
				adj[v].add(u);
			}
			
			HLD hld = new HLD(adj);
			int mx = 0, mi = 0;
			for(int i = 1; i < n; i++) {
				if(hld.depth[i] > mx) {
					mx = hld.depth[i];
					mi = i;
				}
			}
			mx = 0;
			int mi2 = 0;
			for(int i = 0; i < n; i++) {
				if(i == mi) continue;
				int l = hld.lca(mi, i);
				if((hld.depth[mi] + hld.depth[i]) - 2 * hld.depth[l] > mx) {
					mx = (hld.depth[mi] + hld.depth[i]) - 2 * hld.depth[l];
					mi2 = i;
				}
			}
			
			
			ArrayDeque<Integer> leafs = new ArrayDeque<>();
			for(int i = 0; i <n; i++) {
				if(count[i] == 1 && i != mi && i != mi2) {
					leafs.add(i);
				}
			}
			long ans = 0;
			ArrayList<Integer> seq = new ArrayList<>();
			while(!leafs.isEmpty()) {
				int u = leafs.pollLast();
				int l = hld.lca(u, mi);
				int t = hld.depth[mi] + hld.depth[u] - 2*hld.depth[l];
				l = hld.lca(u, mi2);
				int which  = mi;
				if(t <  hld.depth[mi2] + hld.depth[u] - 2*hld.depth[l]) {
					t = hld.depth[mi2] + hld.depth[u] - 2*hld.depth[l];
					which = mi2;
				}
				ans += t;
				for(int v : adj[u]) {
					count[v]--;
					if(count[v] == 1) {
						leafs.add(v);
					}
				}
				seq.add(u);
				seq.add(which);
				seq.add(u);
			}
			
			int l = hld.lca(mi2, mi);
			int dist = hld.depth[mi2] + hld.depth[mi] - 2*hld.depth[l];
			
			while(dist != 0) {
				ans += dist;
				seq.add(mi);
				seq.add(mi2);
				if(mi == l) {
					seq.add(mi2);
					mi2 = hld.parent[mi2];
				} else {
					seq.add(mi);
					mi = hld.parent[mi];
				}
				dist--;
			}
			
			out.println(ans);
			int idx = 0;
			while(idx < seq.size()) {
				out.println((seq.get(idx++)+1) + " " + (seq.get(idx++)+1) +" " + (seq.get(idx++)+1));
			}
			out.close();
		} catch (Exception e) {

		}

	}

	static int depths[], d1[], d2[];
	static int colony[];
	static ArrayList<Integer> depthList[];

	static void dfs(int u, int p, int c, int d) {
		depths[u] = d;
		depthList[d].add(u);
		colony[u] = c;
		if (d1[d] == -1) {
			d1[d] = u;
		} else {
			d2[d] = u;
		}
		for (int v : adj[u]) {
			if (v == p)
				continue;
			dfs(v, u, c, d + 1);
		}
	}

	static long get(int v, ArrayList<Integer> seq) {
		System.out.println(v + 1);
		depths = new int[adj.length];
		colony = new int[adj.length];
		depthList = new ArrayList[adj.length];
		for (int i = 0; i < adj.length; i++)
			depthList[i] = new ArrayList<>();
		d1 = new int[adj.length];
		d2 = new int[adj.length];
		Arrays.fill(d1, -1);
		Arrays.fill(d2, -1);
		depths[v] = 0;
		colony[v] = -1;
		for (int i = 0; i < adj[v].size(); i++) {
			int u = adj[v].get(i);
			dfs(u, v, i + 1, 1);
		}
		int colonyCount[] = new int[adj.length];
		int depthCount[] = new int[adj.length];

		for (int i = 0; i < adj.length; i++) {
			depthCount[depths[i]]++;
			if (colonyCount[depths[i]] == 0) {
				colonyCount[depths[i]] = colony[i];
			} else if (colonyCount[depths[i]] != colony[i]) {
				colonyCount[depths[i]] = -1;
			}
		}
		long ans = 0;
		d1[0] = v;
		// System.out.println(Arrays.toString(depthCount));
		// System.out.println(Arrays.toString(colonyCount));
		depthList[0].add(v);
		// for(int i = 0; i < adj.length; i++) {
		// System.out.println("DEPTH " + i);
		// for(int U : depthList[i]) {
		// System.out.print(U + " ");
		// }System.out.println();
		// }
		for (int i = 1; i < adj.length; i++) {
			if (depthCount[i] > 0) {
				if (colonyCount[i] == -1) {
					for (int j = 0; j < depthList[i].size(); j++) {
						ans += i;
						int node = depthList[i].get(j);
						seq.add(node);
						seq.add(node);
						if (j == 0) {
							ans += i - 1;
							// System.out.println("COL " + d1[i-1] );
							if (colony[d1[i - 1]] == colony[node]) {
								seq.add(d2[i - 1]);
							} else {
								seq.add(d1[i - 1]);
							}
						} else {
							ans += i;
							if (colony[d1[i]] == colony[node]) {
								seq.add(d2[i]);
							} else {
								seq.add(d1[i]);
							}
						}
					}

				} else {
					for (int j = 0; j < depthList[i].size(); j++) {
						int node = depthList[i].get(j);
						ans += i + i - 1;
						seq.add(node);
						seq.add(node);
						if (colony[d1[i - 1]] == colony[node]) {
							seq.add(d2[i - 1]);
						} else {
							seq.add(d1[i - 1]);
						}

					}
				}
			}
		}
		// System.out.println(ans + " " + v);
		Collections.reverse(seq);
		return ans;
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream i) {
			br = new BufferedReader(new InputStreamReader(i));
			st = null;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			if (st == null) {
				st = new StringTokenizer(br.readLine());
			}
			String line = st.nextToken("\n");
			st = null;
			return line;
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	}

	public static class combinatorics {
		static long modInv(long a, long b) {
			return 1 < a ? b - modInv(b % a, a) * b / a : 1;
		}

		static long factorial[], mod;

		combinatorics(int n, long MOD) {
			mod = MOD;
			factorial = new long[n + 1];
			factorial[0] = 1;
			for (int i = 1; i <= n; i++) {
				factorial[i] = i * factorial[i - 1];
				factorial[i] %= mod;
			}
		}

		static long nCr(int n, int r) {
			if (r > n)
				return 0;
			return (factorial[n] * modInv((factorial[n - r] * factorial[r]) % mod, mod)) % mod;
		}
	}

	public static class DisjointSet {
		int p[], r[], s[];
		int numDisjoint;

		DisjointSet(int N) {
			numDisjoint = N;
			r = new int[N];
			s = new int[N];
			p = new int[N];
			for (int i = 0; i < N; i++)
				p[i] = i;
		}

		int findSet(int i) {
			return (p[i] == i) ? i : (p[i] = findSet(p[i]));
		}

		boolean isSameSet(int i, int j) {
			return findSet(i) == findSet(j);
		}

		void unionSet(int i, int j) {
			if (!isSameSet(i, j)) // if from different set
			{
				numDisjoint--;
				int x = findSet(i), y = findSet(j);
				if (r[x] > r[y]) {
					p[y] = x; // rank keeps the tree short
					s[x] += s[y];
				} else {
					p[x] = y;
					if (r[x] == r[y])
						r[y]++;
					s[y] += s[x];
				}
			}
		}

		int sizeOfSet(int i) {
			return s[findSet(i)];
		}
	};

}