#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
long long n, a[3], d[3][maxn], sol;
vector<int> e[maxn], diam;
bool on_diam[maxn];
vector<int> s[3];
int st[maxn], fin[maxn], tick;
void dfs(int t, int x, int par) {
  d[t][x] = d[t][par] + 1;
  for (int i = 0; i < e[x].size(); i++) {
    if (e[x][i] != par) dfs(t, e[x][i], x);
  }
}
bool dfs2(int x, int par) {
  if (x == a[2]) {
    diam.push_back(x);
    on_diam[x] = true;
    return true;
  }
  for (int i = 0; i < e[x].size(); i++) {
    if (e[x][i] != par) {
      if (dfs2(e[x][i], x)) {
        diam.push_back(x);
        on_diam[x] = true;
        return true;
      }
    }
  }
  return false;
}
void dfs2_i_pol(int x, int par) {
  tick++;
  st[x] = tick;
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par) dfs2_i_pol(e[x][i], x);
  fin[x] = tick;
}
inline bool cont(int x) {
  return st[x] <= st[a[1]] && fin[x] >= st[a[1]] && st[x] <= st[a[2]] &&
         fin[x] >= st[a[2]];
}
void dfs3(int x, int par) {
  if (on_diam[x]) {
    for (int i = 0; i < e[x].size(); i++)
      if (e[x][i] != par) dfs3(e[x][i], x);
    return;
  }
  int c = 0;
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par && cont(e[x][i])) c = e[x][i];
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par && e[x][i] != c) dfs3(e[x][i], x);
  s[1].push_back(x);
  s[2].push_back(x);
  if (d[1][x] > d[2][x]) {
    sol += d[1][x] - 1;
    s[0].push_back(a[1]);
  } else {
    sol += d[2][x] - 1;
    s[0].push_back(a[2]);
  }
  if (c != 0) dfs3(c, x);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  int x, y;
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  for (int i = 0; i < 3; i++) {
    a[i] = 1;
    if (i > 0) {
      for (int j = 2; j <= n; j++)
        if (d[i - 1][j] > d[i - 1][a[i]]) a[i] = j;
    }
    dfs(i, a[i], a[i]);
  }
  dfs2(a[1], a[1]);
  dfs2_i_pol(1, 1);
  dfs3(1, 1);
  sol += (long long)diam.size() * (diam.size() - 1) / 2;
  for (int i = diam.size() - 1; i > 0; i--) {
    s[0].push_back(diam[0]);
    s[1].push_back(diam[i]);
    s[2].push_back(diam[i]);
  }
  cout << sol << "\n";
  for (int i = 0; i < n - 1; i++)
    cout << s[0][i] << " " << s[1][i] << " " << s[2][i] << "\n";
  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>
using namespace std;
const int maxn = 2e5 + 10;
long long n, a[3], d[3][maxn], sol;
vector<int> e[maxn], diam;
bool on_diam[maxn];
vector<int> s[3];
int st[maxn], fin[maxn], tick;
void dfs(int t, int x, int par) {
  d[t][x] = d[t][par] + 1;
  for (int i = 0; i < e[x].size(); i++) {
    if (e[x][i] != par) dfs(t, e[x][i], x);
  }
}
bool dfs2(int x, int par) {
  if (x == a[2]) {
    diam.push_back(x);
    on_diam[x] = true;
    return true;
  }
  for (int i = 0; i < e[x].size(); i++) {
    if (e[x][i] != par) {
      if (dfs2(e[x][i], x)) {
        diam.push_back(x);
        on_diam[x] = true;
        return true;
      }
    }
  }
  return false;
}
void dfs2_i_pol(int x, int par) {
  tick++;
  st[x] = tick;
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par) dfs2_i_pol(e[x][i], x);
  fin[x] = tick;
}
inline bool cont(int x) {
  return st[x] <= st[a[1]] && fin[x] >= st[a[1]] && st[x] <= st[a[2]] &&
         fin[x] >= st[a[2]];
}
void dfs3(int x, int par) {
  if (on_diam[x]) {
    for (int i = 0; i < e[x].size(); i++)
      if (e[x][i] != par) dfs3(e[x][i], x);
    return;
  }
  int c = 0;
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par && cont(e[x][i])) c = e[x][i];
  for (int i = 0; i < e[x].size(); i++)
    if (e[x][i] != par && e[x][i] != c) dfs3(e[x][i], x);
  s[1].push_back(x);
  s[2].push_back(x);
  if (d[1][x] > d[2][x]) {
    sol += d[1][x] - 1;
    s[0].push_back(a[1]);
  } else {
    sol += d[2][x] - 1;
    s[0].push_back(a[2]);
  }
  if (c != 0) dfs3(c, x);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  int x, y;
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  for (int i = 0; i < 3; i++) {
    a[i] = 1;
    if (i > 0) {
      for (int j = 2; j <= n; j++)
        if (d[i - 1][j] > d[i - 1][a[i]]) a[i] = j;
    }
    dfs(i, a[i], a[i]);
  }
  dfs2(a[1], a[1]);
  dfs2_i_pol(1, 1);
  dfs3(1, 1);
  sol += (long long)diam.size() * (diam.size() - 1) / 2;
  for (int i = diam.size() - 1; i > 0; i--) {
    s[0].push_back(diam[0]);
    s[1].push_back(diam[i]);
    s[2].push_back(diam[i]);
  }
  cout << sol << "\n";
  for (int i = 0; i < n - 1; i++)
    cout << s[0][i] << " " << s[1][i] << " " << s[2][i] << "\n";
  return 0;
}

```