#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16000000")
using namespace std;
const int Maxn = 200005;
const int Maxm = 21;
const int Maxmy = 500005;
int n;
vector<int> neigh[Maxn];
int L[Maxn], P[Maxn][Maxm];
int distA[Maxn], distB[Maxn];
int trunk[Maxn];
vector<int> my[Maxmy];
long long res;
vector<pair<pair<int, int>, int> > ans;
void Traverse(int v) {
  for (int i = 0; i < neigh[v].size(); i++) {
    int u = neigh[v][i];
    if (u == P[v][0]) continue;
    P[u][0] = v;
    L[u] = L[v] + 1;
    Traverse(u);
  }
}
int getLCA(int a, int b) {
  if (L[a] < L[b]) swap(a, b);
  for (int i = Maxm - 1; i >= 0; i--)
    if (L[a] - (1 << i) >= L[b]) a = P[a][i];
  if (a == b) return a;
  for (int i = Maxm - 1; i >= 0; i--)
    if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
  return P[a][0];
}
int getDist(int a, int b) { return L[a] + L[b] - 2 * L[getLCA(a, b)]; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    neigh[a].push_back(b);
    neigh[b].push_back(a);
  }
  Traverse(1);
  for (int j = 1; j < Maxm; j++)
    for (int i = 1; i <= n; i++) P[i][j] = P[P[i][j - 1]][j - 1];
  int best = -1, a = -1, b = -1;
  for (int i = 1; i <= n; i++) {
    int cand = getDist(1, i);
    if (cand > best) {
      best = cand;
      a = i;
    }
  }
  best = -1;
  for (int i = 1; i <= n; i++) {
    distA[i] = getDist(a, i);
    if (distA[i] > best) {
      best = distA[i];
      b = i;
    }
  }
  for (int i = 1; i <= n; i++) distB[i] = getDist(b, i);
  for (int i = 1; i <= n; i++)
    if (distA[i] + distB[i] == distA[b])
      trunk[distA[i]] = i;
    else
      my[distA[i] + distB[i]].push_back(i);
  for (int i = Maxmy - 1; i >= 0; i--)
    for (int j = 0; j < my[i].size(); j++) {
      int v = my[i][j];
      if (distA[v] >= distB[v]) {
        res += distA[v];
        ans.push_back(pair<pair<int, int>, int>(pair<int, int>(a, v), v));
      } else {
        res += distB[v];
        ans.push_back(pair<pair<int, int>, int>(pair<int, int>(b, v), v));
      }
    }
  for (int i = distA[b]; i > 0; i--) {
    res += i;
    ans.push_back(
        pair<pair<int, int>, int>(pair<int, int>(a, trunk[i]), trunk[i]));
  }
  printf("%I64d\n", res);
  for (int i = 0; i < ans.size(); i++)
    printf("%d %d %d\n", ans[i].first.first, ans[i].first.second,
           ans[i].second);
  return 0;
}

### Prompt

Please create a solution in cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16000000")
using namespace std;
const int Maxn = 200005;
const int Maxm = 21;
const int Maxmy = 500005;
int n;
vector<int> neigh[Maxn];
int L[Maxn], P[Maxn][Maxm];
int distA[Maxn], distB[Maxn];
int trunk[Maxn];
vector<int> my[Maxmy];
long long res;
vector<pair<pair<int, int>, int> > ans;
void Traverse(int v) {
  for (int i = 0; i < neigh[v].size(); i++) {
    int u = neigh[v][i];
    if (u == P[v][0]) continue;
    P[u][0] = v;
    L[u] = L[v] + 1;
    Traverse(u);
  }
}
int getLCA(int a, int b) {
  if (L[a] < L[b]) swap(a, b);
  for (int i = Maxm - 1; i >= 0; i--)
    if (L[a] - (1 << i) >= L[b]) a = P[a][i];
  if (a == b) return a;
  for (int i = Maxm - 1; i >= 0; i--)
    if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
  return P[a][0];
}
int getDist(int a, int b) { return L[a] + L[b] - 2 * L[getLCA(a, b)]; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    neigh[a].push_back(b);
    neigh[b].push_back(a);
  }
  Traverse(1);
  for (int j = 1; j < Maxm; j++)
    for (int i = 1; i <= n; i++) P[i][j] = P[P[i][j - 1]][j - 1];
  int best = -1, a = -1, b = -1;
  for (int i = 1; i <= n; i++) {
    int cand = getDist(1, i);
    if (cand > best) {
      best = cand;
      a = i;
    }
  }
  best = -1;
  for (int i = 1; i <= n; i++) {
    distA[i] = getDist(a, i);
    if (distA[i] > best) {
      best = distA[i];
      b = i;
    }
  }
  for (int i = 1; i <= n; i++) distB[i] = getDist(b, i);
  for (int i = 1; i <= n; i++)
    if (distA[i] + distB[i] == distA[b])
      trunk[distA[i]] = i;
    else
      my[distA[i] + distB[i]].push_back(i);
  for (int i = Maxmy - 1; i >= 0; i--)
    for (int j = 0; j < my[i].size(); j++) {
      int v = my[i][j];
      if (distA[v] >= distB[v]) {
        res += distA[v];
        ans.push_back(pair<pair<int, int>, int>(pair<int, int>(a, v), v));
      } else {
        res += distB[v];
        ans.push_back(pair<pair<int, int>, int>(pair<int, int>(b, v), v));
      }
    }
  for (int i = distA[b]; i > 0; i--) {
    res += i;
    ans.push_back(
        pair<pair<int, int>, int>(pair<int, int>(a, trunk[i]), trunk[i]));
  }
  printf("%I64d\n", res);
  for (int i = 0; i < ans.size(); i++)
    printf("%d %d %d\n", ans[i].first.first, ans[i].first.second,
           ans[i].second);
  return 0;
}

```