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.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class F {
	
	public static int bfs(int start, final int N, int[] costs, ArrayList<HashSet<Integer>> adj){
		Arrays.fill(costs, Integer.MAX_VALUE);
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		queue.add(start); costs[start] = 0;
		
		int last = start;
		while(!queue.isEmpty()){
			final int node = queue.poll();
			last = node;
			
			for(final int next : adj.get(node)){
				if(costs[next] <= costs[node] + 1){ continue; }
				
				queue.add(next); costs[next] = costs[node] + 1;
			}
		}
		
		return last;
	}
	
	public static void main(String[] args) {
		try (final Scanner sc = new Scanner(System.in)) {
			final int N = sc.nextInt();
			ArrayList<HashSet<Integer>> adj = new ArrayList<HashSet<Integer>>();
			for(int i = 0; i < N; i++){ adj.add(new HashSet<Integer>()); }
			
			int[] degs = new int[N];
			for(int i = 0; i < N - 1; i++){
				final int a = sc.nextInt() - 1;
				final int b = sc.nextInt() - 1;
				adj.get(a).add(b);
				adj.get(b).add(a);
				
				degs[a]++; degs[b]++;
			}
			
			
			final int fst = bfs(0, N, new int[N], adj);
			
			final int[] fst_costs = new int[N];
			final int snd = bfs(fst, N, fst_costs, adj);
			
			final int[] snd_costs = new int[N];
			bfs(snd, N, snd_costs, adj);
			//System.out.println((fst + 1) + " " + (snd + 1));
			
			LinkedList<Integer> queue = new LinkedList<Integer>();
			for(int i = 0; i < N; i++){
				if(degs[i] > 1){ continue; }
				if(i == fst || i == snd){ continue; }
				
				queue.add(i);
			}
			//System.out.println(queue);
			
			long answer_cost = 0;
			ArrayList<String> answer = new ArrayList<String>();
			
			while(!queue.isEmpty()){
				final int leaf = queue.poll();
				
				if(fst_costs[leaf] >= snd_costs[leaf]){
					answer_cost += fst_costs[leaf];
					answer.add((leaf + 1) + " " + (fst + 1) + " " + (leaf + 1));
				}else{
					answer_cost += snd_costs[leaf];
					answer.add((leaf + 1) + " " + (snd + 1) + " " + (leaf + 1));
				}
				
				for(final int next : adj.get(leaf)){
					degs[next]--;
					if(degs[next] == 1){ queue.add(next); }
				}
			}
			
			queue.add(snd);
			while(!queue.isEmpty()){
				final int leaf = queue.poll();
				
				answer_cost += fst_costs[leaf];
				answer.add((leaf + 1) + " " + (fst + 1) + " " + (leaf + 1));
				
				for(final int next : adj.get(leaf)){
					degs[next]--;
					if(degs[next] == 1){ queue.add(next); }
				}
			}
			
			try(final PrintWriter pw = new PrintWriter(System.out)){
				pw.println(answer_cost);
				for(final String str : answer){
					pw.println(str);
				}
				pw.flush();
			}
		}
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() {
			try {
				while (!hasNext()) {
					tok = new StringTokenizer(br.readLine());
				}
			} catch (IOException e) { /* ignore */
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}

		public void close() {
			try {
				br.close();
			} catch (IOException e) { /* ignore */
			}
		}
	}
}