#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1), gn(x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1), gn(x2), gn(x3), gn(x4);
}
int head[200011], to[200011 << 1], nxt[200011 << 1];
int E, mx;
int diyi, dier;
int deep[200011], dst[2][200011];
void add(int u, int v) {
  nxt[E] = head[u];
  to[E] = v;
  head[u] = E++;
  nxt[E] = head[v];
  to[E] = u;
  head[v] = E++;
}
void dfs(int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    deep[v] = deep[u] + 1;
    if (deep[v] > mx) diyi = v, mx = deep[v];
    dfs(v, u);
  }
}
void calc(int st, int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    dst[st][v] = dst[st][u] + 1;
    if (!st and dst[st][v] > mx) mx = dst[st][v], dier = v;
    calc(st, v, u);
  }
}
long long ans = 0;
void solve(int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    solve(v, u);
    if (dst[0][v] + dst[1][v] != dst[0][dier]) {
      printf("%d %d %d\n", (dst[0][v] > dst[1][v] ? diyi : dier), v, v);
    }
  }
}
void other(int u, int p = 0) {
  if (u != dier) printf("%d %d %d\n", u, dier, u);
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p or dst[0][v] + dst[1][v] != dst[0][dier]) continue;
    other(v, u);
  }
}
int main() {
  int n;
  cin >> n;
  memset(head, -1, sizeof head);
  for (int u, v, i = 0; i < n - 1; i++) {
    gn(u, v);
    add(u, v);
  }
  dfs(1);
  mx = 0;
  calc(0, diyi);
  calc(1, dier);
  for (int i = 1; i <= n; i++) {
    if (dst[0][i] + dst[1][i] == dst[0][dier])
      ans += dst[0][i];
    else
      ans += max(dst[0][i], dst[1][i]);
  }
  cout << ans << endl;
  solve(diyi);
  other(diyi);
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1), gn(x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1), gn(x2), gn(x3), gn(x4);
}
int head[200011], to[200011 << 1], nxt[200011 << 1];
int E, mx;
int diyi, dier;
int deep[200011], dst[2][200011];
void add(int u, int v) {
  nxt[E] = head[u];
  to[E] = v;
  head[u] = E++;
  nxt[E] = head[v];
  to[E] = u;
  head[v] = E++;
}
void dfs(int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    deep[v] = deep[u] + 1;
    if (deep[v] > mx) diyi = v, mx = deep[v];
    dfs(v, u);
  }
}
void calc(int st, int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    dst[st][v] = dst[st][u] + 1;
    if (!st and dst[st][v] > mx) mx = dst[st][v], dier = v;
    calc(st, v, u);
  }
}
long long ans = 0;
void solve(int u, int p = 0) {
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p) continue;
    solve(v, u);
    if (dst[0][v] + dst[1][v] != dst[0][dier]) {
      printf("%d %d %d\n", (dst[0][v] > dst[1][v] ? diyi : dier), v, v);
    }
  }
}
void other(int u, int p = 0) {
  if (u != dier) printf("%d %d %d\n", u, dier, u);
  for (int v, e = head[u]; ~e; e = nxt[e]) {
    v = to[e];
    if (v == p or dst[0][v] + dst[1][v] != dst[0][dier]) continue;
    other(v, u);
  }
}
int main() {
  int n;
  cin >> n;
  memset(head, -1, sizeof head);
  for (int u, v, i = 0; i < n - 1; i++) {
    gn(u, v);
    add(u, v);
  }
  dfs(1);
  mx = 0;
  calc(0, diyi);
  calc(1, dier);
  for (int i = 1; i <= n; i++) {
    if (dst[0][i] + dst[1][i] == dst[0][dier])
      ans += dst[0][i];
    else
      ans += max(dst[0][i], dst[1][i]);
  }
  cout << ans << endl;
  solve(diyi);
  other(diyi);
  return 0;
}

```