#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma optimize("fast-math")
using namespace std;
vector<vector<int>> vert;
int bfs(int v) {
  queue<int> q;
  vector<bool> was(vert.size(), false);
  q.push(v);
  int last = v;
  was[v] = true;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (int son : vert[now]) {
      if (was[son]) continue;
      q.push(son);
      was[son] = true;
      last = son;
    }
  }
  return last;
}
vector<bool> was;
vector<int> par;
void dfs(int v, int p) {
  was[v] = true;
  par[v] = p;
  for (int son : vert[v]) {
    if (was[son]) continue;
    dfs(son, v);
  }
}
void distfrom(int v, int type, vector<vector<int>> &dist, int nowd) {
  was[v] = true;
  dist[type][v] = nowd;
  for (int son : vert[v]) {
    if (was[son]) continue;
    distfrom(son, type, dist, nowd + 1);
  }
}
vector<vector<int>> dist;
bool comp(int u, int v) {
  return max(dist[0][u], dist[1][u]) > max(dist[0][v], dist[1][v]);
}
struct tup {
  int x, y, z;
};
void solve() {
  int n;
  cin >> n;
  vert.assign(n + 1, vector<int>(0));
  was.assign(n + 1, false);
  par.assign(n + 1, -1);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    vert[a].push_back(b);
    vert[b].push_back(a);
  }
  set<int> last;
  int v = bfs(1);
  int u = bfs(v);
  dfs(v, -1);
  int now = u;
  while (now != -1) {
    last.insert(now);
    now = par[now];
  }
  dist.assign(2, vector<int>(n + 1));
  was.assign(n + 1, false);
  distfrom(v, 0, dist, 0);
  was.assign(n + 1, false);
  distfrom(u, 1, dist, 0);
  vector<int> goodv;
  for (int i = 1; i < n + 1; i++) {
    if (last.find(i) == last.end()) goodv.push_back(i);
  }
  sort((goodv).begin(), (goodv).end(), comp);
  vector<tup> ans;
  long long d = 0;
  for (int kek : goodv) {
    if (dist[0][kek] > dist[1][kek]) {
      ans.push_back({v, kek, kek});
    } else {
      ans.push_back({u, kek, kek});
    }
    d += max(dist[0][kek], dist[1][kek]);
  }
  now = u;
  while (now != v) {
    ans.push_back({now, v, now});
    d += dist[0][now];
    now = par[now];
  }
  cout << d << '\n';
  for (tup &sh : ans) {
    cout << sh.x << " " << sh.y << " " << sh.z << '\n';
  }
}
void testcases(int n) {
  n = 1 - n;
  if (!n) cin >> n;
  for (int i = 0; i < n; i++) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  unsigned int beg_time = clock();
  testcases(0);
  unsigned int end_time = clock();
  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 GCC optimize("O3", "unroll-loops")
#pragma optimize("fast-math")
using namespace std;
vector<vector<int>> vert;
int bfs(int v) {
  queue<int> q;
  vector<bool> was(vert.size(), false);
  q.push(v);
  int last = v;
  was[v] = true;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (int son : vert[now]) {
      if (was[son]) continue;
      q.push(son);
      was[son] = true;
      last = son;
    }
  }
  return last;
}
vector<bool> was;
vector<int> par;
void dfs(int v, int p) {
  was[v] = true;
  par[v] = p;
  for (int son : vert[v]) {
    if (was[son]) continue;
    dfs(son, v);
  }
}
void distfrom(int v, int type, vector<vector<int>> &dist, int nowd) {
  was[v] = true;
  dist[type][v] = nowd;
  for (int son : vert[v]) {
    if (was[son]) continue;
    distfrom(son, type, dist, nowd + 1);
  }
}
vector<vector<int>> dist;
bool comp(int u, int v) {
  return max(dist[0][u], dist[1][u]) > max(dist[0][v], dist[1][v]);
}
struct tup {
  int x, y, z;
};
void solve() {
  int n;
  cin >> n;
  vert.assign(n + 1, vector<int>(0));
  was.assign(n + 1, false);
  par.assign(n + 1, -1);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    vert[a].push_back(b);
    vert[b].push_back(a);
  }
  set<int> last;
  int v = bfs(1);
  int u = bfs(v);
  dfs(v, -1);
  int now = u;
  while (now != -1) {
    last.insert(now);
    now = par[now];
  }
  dist.assign(2, vector<int>(n + 1));
  was.assign(n + 1, false);
  distfrom(v, 0, dist, 0);
  was.assign(n + 1, false);
  distfrom(u, 1, dist, 0);
  vector<int> goodv;
  for (int i = 1; i < n + 1; i++) {
    if (last.find(i) == last.end()) goodv.push_back(i);
  }
  sort((goodv).begin(), (goodv).end(), comp);
  vector<tup> ans;
  long long d = 0;
  for (int kek : goodv) {
    if (dist[0][kek] > dist[1][kek]) {
      ans.push_back({v, kek, kek});
    } else {
      ans.push_back({u, kek, kek});
    }
    d += max(dist[0][kek], dist[1][kek]);
  }
  now = u;
  while (now != v) {
    ans.push_back({now, v, now});
    d += dist[0][now];
    now = par[now];
  }
  cout << d << '\n';
  for (tup &sh : ans) {
    cout << sh.x << " " << sh.y << " " << sh.z << '\n';
  }
}
void testcases(int n) {
  n = 1 - n;
  if (!n) cin >> n;
  for (int i = 0; i < n; i++) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  unsigned int beg_time = clock();
  testcases(0);
  unsigned int end_time = clock();
  return 0;
}

```