#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
void JIZZ() {
  cout << "";
  exit(0);
}
const long double PI = 3.14159265358979323846264338327950288;
const long double eps = 1e-13;
const long long mod = 1e9 + 7;
vector<int> G[200005];
int d[200005], cf[200005], p[20][200005];
queue<int> isleaf;
bitset<200006> exist;
int child[200005];
void dfs(int now, int pa, int dis) {
  d[now] = dis;
  cf[now] = pa;
  for (int i : G[now]) {
    if (i != pa) {
      dfs(i, now, dis + 1);
    }
  }
}
void dfs1(int now, int pa, int dep) {
  d[now] = dep;
  p[0][now] = pa;
  for (int i = 1; (1 << i) <= dep; ++i) {
    p[i][now] = p[i - 1][p[i - 1][now]];
  }
  bool isl = 1;
  for (int i : G[now]) {
    if (i != pa) {
      isl = 0;
      dfs1(i, now, dep + 1);
      ++child[now];
    }
  }
  if (isl) isleaf.push(now);
}
int lca(int pa, int push_back) {
  if (pa == push_back) exit(5487);
  if (d[pa] > d[push_back]) swap(pa, push_back);
  for (int i = 18; i >= 0; --i) {
    if ((1 << i) & (d[push_back] - d[pa])) {
      push_back = p[i][push_back];
    }
  }
  if (pa == push_back) return pa;
  for (int i = 18; i >= 0; --i) {
    if (p[i][pa] != p[i][push_back]) {
      pa = p[i][pa];
      push_back = p[i][push_back];
    }
  }
  if (p[0][pa] != p[0][push_back]) exit(408);
  return p[0][pa];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  if (n == 2) return cout << "1\n1 2 2\n", 0;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0, 0);
  int farest = 0, far;
  for (int i = 1; i <= n; ++i)
    if (d[i] > farest) farest = d[i], far = i;
  dfs(far, 0, 0);
  farest = 0;
  int end1 = far;
  for (int i = 1; i <= n; ++i)
    if (d[i] > farest) farest = d[i], far = i;
  int root = cf[far];
  int end2 = far;
  dfs1(root, 0, 1);
  long long ans = 0;
  vector<int> anss;
  ;
  ;
  exist.set();
  while (isleaf.size()) {
    int i = isleaf.front();
    isleaf.pop();
    if (i == end1 || i == end2) continue;
    int lca1 = lca(i, end1);
    int lca2 = lca(i, end2);
    int dis1 = d[i] + d[end1] - 2 * d[lca1];
    int dis2 = d[i] + d[end2] - 2 * d[lca2];
    if (lca1 == i || lca2 == i) continue;
    if (dis1 > dis2) {
      ans += dis1;
      anss.push_back(i);
      anss.push_back(end1);
      anss.push_back(i);
    } else {
      ans += dis2;
      anss.push_back(i);
      anss.push_back(end2);
      anss.push_back(i);
    }
    exist[i] = 0;
    --child[p[0][i]];
    if (child[p[0][i]] == 0) {
      isleaf.push(p[0][i]);
    }
  }
  while (end2 != end1) {
    ans += farest;
    --farest;
    anss.push_back(end2);
    anss.push_back(end1);
    anss.push_back(end2);
    end2 = cf[end2];
  }
  cout << ans << endl;
  for (int i = 0; i < anss.size(); i += 3) {
    cout << anss[i] << " " << anss[i + 1] << " " << anss[i + 2] << '\n';
  }
}

### 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:36777216")
using namespace std;
void JIZZ() {
  cout << "";
  exit(0);
}
const long double PI = 3.14159265358979323846264338327950288;
const long double eps = 1e-13;
const long long mod = 1e9 + 7;
vector<int> G[200005];
int d[200005], cf[200005], p[20][200005];
queue<int> isleaf;
bitset<200006> exist;
int child[200005];
void dfs(int now, int pa, int dis) {
  d[now] = dis;
  cf[now] = pa;
  for (int i : G[now]) {
    if (i != pa) {
      dfs(i, now, dis + 1);
    }
  }
}
void dfs1(int now, int pa, int dep) {
  d[now] = dep;
  p[0][now] = pa;
  for (int i = 1; (1 << i) <= dep; ++i) {
    p[i][now] = p[i - 1][p[i - 1][now]];
  }
  bool isl = 1;
  for (int i : G[now]) {
    if (i != pa) {
      isl = 0;
      dfs1(i, now, dep + 1);
      ++child[now];
    }
  }
  if (isl) isleaf.push(now);
}
int lca(int pa, int push_back) {
  if (pa == push_back) exit(5487);
  if (d[pa] > d[push_back]) swap(pa, push_back);
  for (int i = 18; i >= 0; --i) {
    if ((1 << i) & (d[push_back] - d[pa])) {
      push_back = p[i][push_back];
    }
  }
  if (pa == push_back) return pa;
  for (int i = 18; i >= 0; --i) {
    if (p[i][pa] != p[i][push_back]) {
      pa = p[i][pa];
      push_back = p[i][push_back];
    }
  }
  if (p[0][pa] != p[0][push_back]) exit(408);
  return p[0][pa];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  if (n == 2) return cout << "1\n1 2 2\n", 0;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0, 0);
  int farest = 0, far;
  for (int i = 1; i <= n; ++i)
    if (d[i] > farest) farest = d[i], far = i;
  dfs(far, 0, 0);
  farest = 0;
  int end1 = far;
  for (int i = 1; i <= n; ++i)
    if (d[i] > farest) farest = d[i], far = i;
  int root = cf[far];
  int end2 = far;
  dfs1(root, 0, 1);
  long long ans = 0;
  vector<int> anss;
  ;
  ;
  exist.set();
  while (isleaf.size()) {
    int i = isleaf.front();
    isleaf.pop();
    if (i == end1 || i == end2) continue;
    int lca1 = lca(i, end1);
    int lca2 = lca(i, end2);
    int dis1 = d[i] + d[end1] - 2 * d[lca1];
    int dis2 = d[i] + d[end2] - 2 * d[lca2];
    if (lca1 == i || lca2 == i) continue;
    if (dis1 > dis2) {
      ans += dis1;
      anss.push_back(i);
      anss.push_back(end1);
      anss.push_back(i);
    } else {
      ans += dis2;
      anss.push_back(i);
      anss.push_back(end2);
      anss.push_back(i);
    }
    exist[i] = 0;
    --child[p[0][i]];
    if (child[p[0][i]] == 0) {
      isleaf.push(p[0][i]);
    }
  }
  while (end2 != end1) {
    ans += farest;
    --farest;
    anss.push_back(end2);
    anss.push_back(end1);
    anss.push_back(end2);
    end2 = cf[end2];
  }
  cout << ans << endl;
  for (int i = 0; i < anss.size(); i += 3) {
    cout << anss[i] << " " << anss[i + 1] << " " << anss[i + 2] << '\n';
  }
}

```