#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
template <typename T1, typename T2>
inline void chmin(T1 &a, const T2 &b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, const T2 &b) {
  if (a < b) a = b;
}
template <typename T>
pair<T, int> dfs(const vector<vector<pair<int, T>>> &g, int idx, int par) {
  pair<T, int> ret(0, idx);
  for (auto &e : g[idx]) {
    if (e.first == par) continue;
    auto cost = dfs(g, e.first, idx);
    cost.first += e.second;
    ret = max(ret, cost);
  }
  return ret;
}
template <typename T>
pair<int, int> tree_diameter(const vector<vector<pair<int, T>>> &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return {p.second, q.second};
}
template <typename T>
vector<pair<T, int>> dijkstra(vector<vector<pair<int, T>>> &g, int s) {
  int n = g.size();
  const auto inf = numeric_limits<T>::max();
  vector<pair<T, int>> dist(n, {inf, -1});
  using P = pair<T, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  dist[s] = {0, -1};
  que.emplace(dist[s].first, s);
  while (!que.empty()) {
    T cost;
    int node;
    tie(cost, node) = que.top();
    que.pop();
    if (dist[node].first < cost) continue;
    for (auto &e : g[node]) {
      auto next_cost = cost + e.second;
      int next_node = e.first;
      if (dist[next_node].first <= next_cost) continue;
      dist[next_node] = {next_cost, node};
      que.emplace(next_cost, next_node);
    }
  }
  return dist;
}
int main() {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back({b, 1});
    g[b].push_back({a, 1});
  }
  int p, q;
  tie(p, q) = tree_diameter(g);
  auto fp = dijkstra(g, p);
  auto fq = dijkstra(g, q);
  lint ans = 0;
  vector<pair<pair<int, int>, pair<int, int>>> hoge;
  for (int x = 0; x < n; x++) {
    if (fp[x].first + fq[x].first == fp[q].first) continue;
    ans += max(fp[x].first, fq[x].first);
    if (fp[x].first > fq[x].first) {
      hoge.push_back({{-fp[x].first, p}, {x, x}});
    } else {
      hoge.push_back({{-fq[x].first, q}, {x, x}});
    }
  }
  sort(hoge.begin(), hoge.end());
  lint d = fp[q].first;
  ans += d * (d + 1) / 2;
  vector<pair<int, int>> vp;
  for (int x = 0; x < n; x++) {
    if (fp[x].first + fq[x].first == fp[q].first) {
      vp.push_back({fp[x].first, x});
    }
  }
  sort(vp.begin(), vp.end());
  for (auto e : vp) {
    hoge.push_back({{-1, q}, {e.second, e.second}});
  }
  cerr << "p = " << p << ", q = " << q << endl;
  cout << ans << endl;
  for (int i = 0; i < hoge.size() - 1; i++) {
    auto e = hoge[i];
    cout << e.first.second + 1 << " " << e.second.first + 1 << " "
         << e.second.second + 1 << endl;
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
template <typename T1, typename T2>
inline void chmin(T1 &a, const T2 &b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, const T2 &b) {
  if (a < b) a = b;
}
template <typename T>
pair<T, int> dfs(const vector<vector<pair<int, T>>> &g, int idx, int par) {
  pair<T, int> ret(0, idx);
  for (auto &e : g[idx]) {
    if (e.first == par) continue;
    auto cost = dfs(g, e.first, idx);
    cost.first += e.second;
    ret = max(ret, cost);
  }
  return ret;
}
template <typename T>
pair<int, int> tree_diameter(const vector<vector<pair<int, T>>> &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return {p.second, q.second};
}
template <typename T>
vector<pair<T, int>> dijkstra(vector<vector<pair<int, T>>> &g, int s) {
  int n = g.size();
  const auto inf = numeric_limits<T>::max();
  vector<pair<T, int>> dist(n, {inf, -1});
  using P = pair<T, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  dist[s] = {0, -1};
  que.emplace(dist[s].first, s);
  while (!que.empty()) {
    T cost;
    int node;
    tie(cost, node) = que.top();
    que.pop();
    if (dist[node].first < cost) continue;
    for (auto &e : g[node]) {
      auto next_cost = cost + e.second;
      int next_node = e.first;
      if (dist[next_node].first <= next_cost) continue;
      dist[next_node] = {next_cost, node};
      que.emplace(next_cost, next_node);
    }
  }
  return dist;
}
int main() {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back({b, 1});
    g[b].push_back({a, 1});
  }
  int p, q;
  tie(p, q) = tree_diameter(g);
  auto fp = dijkstra(g, p);
  auto fq = dijkstra(g, q);
  lint ans = 0;
  vector<pair<pair<int, int>, pair<int, int>>> hoge;
  for (int x = 0; x < n; x++) {
    if (fp[x].first + fq[x].first == fp[q].first) continue;
    ans += max(fp[x].first, fq[x].first);
    if (fp[x].first > fq[x].first) {
      hoge.push_back({{-fp[x].first, p}, {x, x}});
    } else {
      hoge.push_back({{-fq[x].first, q}, {x, x}});
    }
  }
  sort(hoge.begin(), hoge.end());
  lint d = fp[q].first;
  ans += d * (d + 1) / 2;
  vector<pair<int, int>> vp;
  for (int x = 0; x < n; x++) {
    if (fp[x].first + fq[x].first == fp[q].first) {
      vp.push_back({fp[x].first, x});
    }
  }
  sort(vp.begin(), vp.end());
  for (auto e : vp) {
    hoge.push_back({{-1, q}, {e.second, e.second}});
  }
  cerr << "p = " << p << ", q = " << q << endl;
  cout << ans << endl;
  for (int i = 0; i < hoge.size() - 1; i++) {
    auto e = hoge[i];
    cout << e.first.second + 1 << " " << e.second.first + 1 << " "
         << e.second.second + 1 << endl;
  }
  return 0;
}

```