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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
unordered_map<long long, vector<long long> > graph;
long long visited[200001];
long long a, b;
long long n;
long long mx_dist;
long long mx_vertex;
long long mx_vertex2;
vector<long long> diameter_path;
long long on_path[200001];
long long stay = -1;
long long starting;
struct op {
  long long aa, bb, cc;
};
op operations[200001];
long long ok;
long long orig;
void dfs(long long curr, long long dist) {
  if (visited[curr]) return;
  if (dist > mx_dist) {
    mx_dist = dist;
    mx_vertex = curr;
  }
  visited[curr] = 1;
  for (long long i = 0; i < graph[curr].size(); i++) {
    dfs(graph[curr][i], dist + 1);
  }
}
void dfs2(long long curr, long long dist) {
  if (visited[curr]) return;
  if (dist > mx_dist) {
    mx_dist = dist;
    mx_vertex2 = curr;
  }
  visited[curr] = 1;
  for (long long i = 0; i < graph[curr].size(); i++) {
    dfs2(graph[curr][i], dist + 1);
  }
}
long long dfs3(long long curr) {
  if (curr == mx_vertex2) {
    diameter_path.emplace_back(curr);
    return 1;
  }
  if (visited[curr]) return 0;
  visited[curr] = 1;
  bool on_path = 0;
  long long val;
  for (long long i = 0; i < graph[curr].size() && !on_path; i++) {
    on_path = dfs3(graph[curr][i]);
  }
  if (on_path) {
    diameter_path.emplace_back(curr);
  }
  return on_path;
}
unordered_map<long long, long long> mm;
void dfs4(long long curr, long long dist) {
  if (visited[curr] || on_path[curr]) return;
  visited[curr] = 1;
  for (long long i = 0; i < graph[curr].size(); i++) {
    dfs4(graph[curr][i], dist + 1);
  }
  if (dist > orig) {
    if (mm.find(dist) == mm.end()) {
      mm[dist] = 0;
    }
    mm[dist]++;
  }
  if (curr != starting) {
    operations[ok].aa = stay;
    operations[ok].bb = curr;
    operations[ok].cc = curr;
    ok++;
  }
  return;
}
long long tri(long long num) { return num * (num + 1) / 2; }
int main() {
  mx_dist = 0;
  mx_vertex = 0;
  mx_vertex2 = 0;
  scanf("%I64d", &n);
  for (long long i = 0; i < n - 1; i++) {
    scanf("%I64d %I64d", &a, &b);
    graph[a].emplace_back(b);
    graph[b].emplace_back(a);
  }
  for (long long i = 0; i <= n; i++) {
    visited[i] = 0;
  }
  dfs(1, 1);
  for (long long i = 0; i <= n; i++) {
    visited[i] = 0;
  }
  mx_dist = 0;
  dfs2(mx_vertex, 1);
  for (long long i = 0; i <= n; i++) {
    on_path[i] = 0;
    visited[i] = 0;
  }
  dfs3(mx_vertex);
  for (long long i = 0; i < diameter_path.size(); i++) {
    on_path[diameter_path[i]] = 1;
  }
  for (long long i = 0; i <= n; i++) {
    visited[i] = 0;
  }
  long long lhs, rhs;
  lhs = diameter_path[0];
  rhs = diameter_path[diameter_path.size() - 1];
  long long sum = 0;
  for (long long i = 0; i < diameter_path.size(); i++) {
    on_path[diameter_path[i]] = 0;
    if (i + 1 > mx_dist - i) {
      stay = lhs;
    } else {
      stay = rhs;
    }
    starting = diameter_path[i];
    orig = max(i, mx_dist - i - 1);
    dfs4(diameter_path[i], max(i, mx_dist - i - 1));
    on_path[diameter_path[i]] = 1;
    unordered_map<long long, long long>::iterator mit;
    for (mit = mm.begin(); mit != mm.end(); mit++) {
      sum += (mit->first) * (mit->second);
    }
    mm.clear();
  }
  sum += tri(mx_dist - 1);
  for (long long i = 0; i < diameter_path.size() - 1; i++) {
    operations[ok].aa = diameter_path[i];
    operations[ok].bb = diameter_path[diameter_path.size() - 1];
    operations[ok].cc = diameter_path[i];
    ok++;
  }
  printf("%I64d\n", sum);
  for (long long i = 0; i < ok; i++) {
    printf("%I64d %I64d %I64d\n", operations[i].aa, operations[i].bb,
           operations[i].cc);
  }
  return 0;
}