#include <bits/stdc++.h>
using namespace std;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
template <typename T, typename U>
inline void mnze(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void mxze(T &x, U y) {
  if (x < y) x = y;
}
void _scan(int &x) { scanf("%d", &x); }
void _scan(long long &x) { scanf("%lld", &x); }
void _scan(double &x) { scanf("%lf", &x); }
void _scan(char &x) { scanf(" %c", &x); }
void _scan(char *x) { scanf("%s", x); }
void scan() {}
template <typename T, typename... U>
void scan(T &head, U &...tail) {
  _scan(head);
  scan(tail...);
}
template <typename T>
void _dbg(const char *sdbg, T h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename T, typename... U>
void _dbg(const char *sdbg, T h, U... t) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
const int MAXN = 2e5 + 5;
int n, dx[MAXN], dy[MAXN];
vector<int> G[MAXN];
int bfs(int s, int d[MAXN]) {
  memset(d, -1, sizeof(d[0]) * (n + 1));
  queue<int> q;
  q.push(s);
  d[s] = 0;
  int v;
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (int u : G[v]) {
      if (d[u] == -1) {
        d[u] = d[v] + 1;
        q.push(u);
      }
    }
  }
  return v;
}
bool ond[MAXN], found = false;
stack<int> stk;
queue<int> stk2;
void findpath(int v, int p, int y) {
  ond[v] = true;
  stk.push(v);
  if (v == y) {
    found = true;
    return;
  }
  for (int u : G[v]) {
    if (u == p) continue;
    findpath(u, v, y);
    if (found) return;
  }
  ond[v] = false;
  stk.pop();
}
void dfs(int v, int p) {
  for (int u : G[v]) {
    if (u == p) continue;
    dfs(u, v);
  }
  if (!ond[v]) stk2.push(v);
}
int main() {
  scan(n);
  for (int i = 0; i < (int)n - 1; i++) {
    int v, u;
    scan(v, u);
    v--;
    u--;
    G[v].push_back(u);
    G[u].push_back(v);
  }
  int x = bfs(0, dx);
  int y = bfs(x, dx);
  bfs(y, dy);
  findpath(x, -1, y);
  dfs(x, -1);
  long long ans = 0;
  for (int v = 0; v < (int)n; v++) {
    if (ond[v]) continue;
    ans += max(dx[v], dy[v]);
  }
  long long d = dx[y];
  ans += d * (d + 1) / 2;
  printf("%lld\n", ans);
  while (!stk2.empty()) {
    int v = stk2.front();
    stk2.pop();
    int b = x, bd = dx[v];
    if (dy[v] > bd) {
      bd = dy[v];
      b = y;
    }
    printf("%d %d %d\n", v + 1, b + 1, v + 1);
  }
  while (true) {
    int v = stk.top();
    stk.pop();
    if (stk.empty()) break;
    printf("%d %d %d\n", v + 1, x + 1, v + 1);
  }
}

### Prompt

Generate a Cpp solution 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;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
template <typename T, typename U>
inline void mnze(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void mxze(T &x, U y) {
  if (x < y) x = y;
}
void _scan(int &x) { scanf("%d", &x); }
void _scan(long long &x) { scanf("%lld", &x); }
void _scan(double &x) { scanf("%lf", &x); }
void _scan(char &x) { scanf(" %c", &x); }
void _scan(char *x) { scanf("%s", x); }
void scan() {}
template <typename T, typename... U>
void scan(T &head, U &...tail) {
  _scan(head);
  scan(tail...);
}
template <typename T>
void _dbg(const char *sdbg, T h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename T, typename... U>
void _dbg(const char *sdbg, T h, U... t) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
const int MAXN = 2e5 + 5;
int n, dx[MAXN], dy[MAXN];
vector<int> G[MAXN];
int bfs(int s, int d[MAXN]) {
  memset(d, -1, sizeof(d[0]) * (n + 1));
  queue<int> q;
  q.push(s);
  d[s] = 0;
  int v;
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (int u : G[v]) {
      if (d[u] == -1) {
        d[u] = d[v] + 1;
        q.push(u);
      }
    }
  }
  return v;
}
bool ond[MAXN], found = false;
stack<int> stk;
queue<int> stk2;
void findpath(int v, int p, int y) {
  ond[v] = true;
  stk.push(v);
  if (v == y) {
    found = true;
    return;
  }
  for (int u : G[v]) {
    if (u == p) continue;
    findpath(u, v, y);
    if (found) return;
  }
  ond[v] = false;
  stk.pop();
}
void dfs(int v, int p) {
  for (int u : G[v]) {
    if (u == p) continue;
    dfs(u, v);
  }
  if (!ond[v]) stk2.push(v);
}
int main() {
  scan(n);
  for (int i = 0; i < (int)n - 1; i++) {
    int v, u;
    scan(v, u);
    v--;
    u--;
    G[v].push_back(u);
    G[u].push_back(v);
  }
  int x = bfs(0, dx);
  int y = bfs(x, dx);
  bfs(y, dy);
  findpath(x, -1, y);
  dfs(x, -1);
  long long ans = 0;
  for (int v = 0; v < (int)n; v++) {
    if (ond[v]) continue;
    ans += max(dx[v], dy[v]);
  }
  long long d = dx[y];
  ans += d * (d + 1) / 2;
  printf("%lld\n", ans);
  while (!stk2.empty()) {
    int v = stk2.front();
    stk2.pop();
    int b = x, bd = dx[v];
    if (dy[v] > bd) {
      bd = dy[v];
      b = y;
    }
    printf("%d %d %d\n", v + 1, b + 1, v + 1);
  }
  while (true) {
    int v = stk.top();
    stk.pop();
    if (stk.empty()) break;
    printf("%d %d %d\n", v + 1, x + 1, v + 1);
  }
}

```