#include <bits/stdc++.h>
using namespace std;
struct node {
  int a, b, c;
  node(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
};
vector<int> adj[200005];
int ht[200005], far[200005];
int d[2][200005];
bool del[200005];
int dia, dv1, dv2;
int n;
void diameter(int now, int parent, int& dlen, int& v1, int& v2, int& root) {
  ht[now] = 0;
  far[now] = now;
  for (int child : adj[now]) {
    if (child == parent) continue;
    diameter(child, now, dlen, v1, v2, root);
    if (ht[child] + 1 > ht[now]) {
      ht[now] = ht[child] + 1;
      far[now] = far[child];
    }
  }
  int f1 = -1;
  int maxht = -1;
  for (int child : adj[now]) {
    if (child == parent) continue;
    if (ht[child] > maxht) {
      maxht = ht[child];
      f1 = child;
    }
  }
  int f2 = -1;
  maxht = -1;
  for (int child : adj[now]) {
    if (child == parent) continue;
    if (ht[child] > maxht && child != f1) {
      maxht = ht[child];
      f2 = child;
    }
  }
  int nowd;
  if (f1 == -1) {
    assert(f2 == -1);
    f1 = f2 = now;
    nowd = 0;
  } else if (f2 == -1) {
    f2 = now;
    nowd = ht[f1] + 1;
    f1 = far[f1];
  } else {
    nowd = ht[f1] + ht[f2] + 2;
    f1 = far[f1];
    f2 = far[f2];
  }
  if (nowd > dlen) {
    dlen = nowd;
    v1 = f1;
    v2 = f2;
    root = now;
  }
}
void dfs_dist(int res[], int now, int parent, int len) {
  res[now] = len;
  for (int child : adj[now]) {
    if (child == parent) continue;
    dfs_dist(res, child, now, len + 1);
  }
}
void dfs_solve(vector<node>& op, int now, int parent, long long int& res) {
  if (now == dv1 || now == dv2) return;
  del[now] = true;
  for (int child : adj[now]) {
    if (child == parent) continue;
    dfs_solve(op, child, now, res);
    if (!del[child]) del[now] = false;
  }
  if (del[now]) {
    int partner = (d[0][now] >= d[1][now] ? dv1 : dv2);
    res += max(d[0][now], d[1][now]);
    op.emplace_back(now, partner, now);
  }
}
int main(int argc, char* argv[]) {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int root;
  dia = -1;
  diameter(1, -1, dia, dv1, dv2, root);
  ;
  dfs_dist(d[0], dv1, -1, 0);
  dfs_dist(d[1], dv2, -1, 0);
  assert(d[0][dv2] == dia);
  assert(d[1][dv1] == dia);
  vector<node> oseq;
  long long int ans = 0ll;
  dfs_solve(oseq, root, -1, ans);
  assert(!del[dv1]);
  assert(!del[dv2]);
  int now = dv1;
  while (now != dv2) {
    ans += dia--;
    oseq.emplace_back(now, dv2, now);
    del[now] = true;
    for (int child : adj[now]) {
      if (!del[child]) {
        now = child;
        break;
      }
    }
  }
  assert(dia == 0);
  assert((int)oseq.size() == n - 1);
  printf("%lld\n", ans);
  for (const node& nd : oseq) printf("%d %d %d\n", nd.a, nd.b, nd.c);
  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;
struct node {
  int a, b, c;
  node(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
};
vector<int> adj[200005];
int ht[200005], far[200005];
int d[2][200005];
bool del[200005];
int dia, dv1, dv2;
int n;
void diameter(int now, int parent, int& dlen, int& v1, int& v2, int& root) {
  ht[now] = 0;
  far[now] = now;
  for (int child : adj[now]) {
    if (child == parent) continue;
    diameter(child, now, dlen, v1, v2, root);
    if (ht[child] + 1 > ht[now]) {
      ht[now] = ht[child] + 1;
      far[now] = far[child];
    }
  }
  int f1 = -1;
  int maxht = -1;
  for (int child : adj[now]) {
    if (child == parent) continue;
    if (ht[child] > maxht) {
      maxht = ht[child];
      f1 = child;
    }
  }
  int f2 = -1;
  maxht = -1;
  for (int child : adj[now]) {
    if (child == parent) continue;
    if (ht[child] > maxht && child != f1) {
      maxht = ht[child];
      f2 = child;
    }
  }
  int nowd;
  if (f1 == -1) {
    assert(f2 == -1);
    f1 = f2 = now;
    nowd = 0;
  } else if (f2 == -1) {
    f2 = now;
    nowd = ht[f1] + 1;
    f1 = far[f1];
  } else {
    nowd = ht[f1] + ht[f2] + 2;
    f1 = far[f1];
    f2 = far[f2];
  }
  if (nowd > dlen) {
    dlen = nowd;
    v1 = f1;
    v2 = f2;
    root = now;
  }
}
void dfs_dist(int res[], int now, int parent, int len) {
  res[now] = len;
  for (int child : adj[now]) {
    if (child == parent) continue;
    dfs_dist(res, child, now, len + 1);
  }
}
void dfs_solve(vector<node>& op, int now, int parent, long long int& res) {
  if (now == dv1 || now == dv2) return;
  del[now] = true;
  for (int child : adj[now]) {
    if (child == parent) continue;
    dfs_solve(op, child, now, res);
    if (!del[child]) del[now] = false;
  }
  if (del[now]) {
    int partner = (d[0][now] >= d[1][now] ? dv1 : dv2);
    res += max(d[0][now], d[1][now]);
    op.emplace_back(now, partner, now);
  }
}
int main(int argc, char* argv[]) {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int root;
  dia = -1;
  diameter(1, -1, dia, dv1, dv2, root);
  ;
  dfs_dist(d[0], dv1, -1, 0);
  dfs_dist(d[1], dv2, -1, 0);
  assert(d[0][dv2] == dia);
  assert(d[1][dv1] == dia);
  vector<node> oseq;
  long long int ans = 0ll;
  dfs_solve(oseq, root, -1, ans);
  assert(!del[dv1]);
  assert(!del[dv2]);
  int now = dv1;
  while (now != dv2) {
    ans += dia--;
    oseq.emplace_back(now, dv2, now);
    del[now] = true;
    for (int child : adj[now]) {
      if (!del[child]) {
        now = child;
        break;
      }
    }
  }
  assert(dia == 0);
  assert((int)oseq.size() == n - 1);
  printf("%lld\n", ans);
  for (const node& nd : oseq) printf("%d %d %d\n", nd.a, nd.b, nd.c);
  return 0;
}

```