#include <bits/stdc++.h>
using namespace std;
vector<vector<long long>> v(200010);
class Dijkstra {
 public:
  struct edge {
    long long v, dist;
  };
  struct state {
    long long v, cost;
    bool operator>(const state s) const { return cost > s.cost; }
  };
  const long long INF = (1LL << 60);
  long long N;
  vector<vector<edge>> E;
  Dijkstra(long long n) : N(n), E(n) {}
  void add_directed_edge(long long u, long long v, long long d) {
    E[u].push_back((edge){v, d});
  }
  void add_undirected_edge(long long u, long long v, long long d) {
    E[u].push_back((edge){v, d});
    E[v].push_back((edge){u, d});
  }
  vector<long long> shortest_path(long long S) {
    vector<long long> dp(E.size(), INF);
    priority_queue<state, vector<state>, greater<state>> q;
    q.push((state){S, 0});
    while (!q.empty()) {
      long long v = q.top().v, cost = q.top().cost;
      q.pop();
      if (dp[v] <= cost) continue;
      dp[v] = cost;
      for (long long i = 0; i < E[v].size(); i++) {
        long long nv = E[v][i].v, ncost = cost + E[v][i].dist;
        if (dp[nv] > ncost) q.push((state){nv, ncost});
      }
    }
    return dp;
  }
};
long long ma, l, r;
long long sum = 0;
vector<long long> L, R;
vector<array<long long, 3>> ans;
bool used[200010];
bool dfs(long long p) {
  bool ret = false;
  used[p] = 1;
  if (p != l && p != r && v[p].size() == 1) {
    if (L[p] > R[p]) {
      ans.push_back({p, l, p});
      sum += L[p];
    } else {
      ans.push_back({p, r, p});
      sum += R[p];
    }
    return true;
  }
  if (p == r) return false;
  for (auto i : v[p]) {
    if (!used[i]) {
      ret |= dfs(i);
    }
  }
  if (p != l && p != r && ret) {
    if (ma != R[p] + L[p]) {
      if (L[p] > R[p]) {
        ans.push_back({p, l, p});
        sum += L[p];
      } else {
        ans.push_back({p, r, p});
        sum += R[p];
      }
    }
  }
  return ret;
}
bool dfs2(long long p) {
  used[p] = 1;
  bool ret = false;
  if (p == r) {
    sum += L[r];
    ans.push_back({l, r, r});
    return true;
  }
  for (auto i : v[p]) {
    if (!used[i]) {
      ret |= dfs2(i);
    }
  }
  if (p != l && ret) {
    sum += L[p];
    ans.push_back({l, p, p});
  }
  return ret;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  long long n;
  cin >> n;
  Dijkstra d(n);
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    a--, b--;
    v[a].push_back(b);
    v[b].push_back(a);
    d.add_undirected_edge(a, b, 1);
  }
  vector<long long> p = d.shortest_path(0);
  for (long long i = 0; i < n; i++) {
    if (ma < p[i]) {
      ma = p[i];
      l = i;
    }
  }
  ma = 0;
  L = d.shortest_path(l);
  for (long long i = 0; i < n; i++) {
    if (ma < L[i]) {
      ma = L[i];
      r = i;
    }
  }
  R = d.shortest_path(r);
  dfs(l);
  for (long long i = 0; i < n; i++) used[i] = false;
  dfs2(l);
  cout << sum << endl;
  for (auto i : ans) {
    cout << i[0] + 1 << " " << i[1] + 1 << " " << i[2] + 1 << "\n";
  }
}

### Prompt

Your task is to create 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;
vector<vector<long long>> v(200010);
class Dijkstra {
 public:
  struct edge {
    long long v, dist;
  };
  struct state {
    long long v, cost;
    bool operator>(const state s) const { return cost > s.cost; }
  };
  const long long INF = (1LL << 60);
  long long N;
  vector<vector<edge>> E;
  Dijkstra(long long n) : N(n), E(n) {}
  void add_directed_edge(long long u, long long v, long long d) {
    E[u].push_back((edge){v, d});
  }
  void add_undirected_edge(long long u, long long v, long long d) {
    E[u].push_back((edge){v, d});
    E[v].push_back((edge){u, d});
  }
  vector<long long> shortest_path(long long S) {
    vector<long long> dp(E.size(), INF);
    priority_queue<state, vector<state>, greater<state>> q;
    q.push((state){S, 0});
    while (!q.empty()) {
      long long v = q.top().v, cost = q.top().cost;
      q.pop();
      if (dp[v] <= cost) continue;
      dp[v] = cost;
      for (long long i = 0; i < E[v].size(); i++) {
        long long nv = E[v][i].v, ncost = cost + E[v][i].dist;
        if (dp[nv] > ncost) q.push((state){nv, ncost});
      }
    }
    return dp;
  }
};
long long ma, l, r;
long long sum = 0;
vector<long long> L, R;
vector<array<long long, 3>> ans;
bool used[200010];
bool dfs(long long p) {
  bool ret = false;
  used[p] = 1;
  if (p != l && p != r && v[p].size() == 1) {
    if (L[p] > R[p]) {
      ans.push_back({p, l, p});
      sum += L[p];
    } else {
      ans.push_back({p, r, p});
      sum += R[p];
    }
    return true;
  }
  if (p == r) return false;
  for (auto i : v[p]) {
    if (!used[i]) {
      ret |= dfs(i);
    }
  }
  if (p != l && p != r && ret) {
    if (ma != R[p] + L[p]) {
      if (L[p] > R[p]) {
        ans.push_back({p, l, p});
        sum += L[p];
      } else {
        ans.push_back({p, r, p});
        sum += R[p];
      }
    }
  }
  return ret;
}
bool dfs2(long long p) {
  used[p] = 1;
  bool ret = false;
  if (p == r) {
    sum += L[r];
    ans.push_back({l, r, r});
    return true;
  }
  for (auto i : v[p]) {
    if (!used[i]) {
      ret |= dfs2(i);
    }
  }
  if (p != l && ret) {
    sum += L[p];
    ans.push_back({l, p, p});
  }
  return ret;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  long long n;
  cin >> n;
  Dijkstra d(n);
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    a--, b--;
    v[a].push_back(b);
    v[b].push_back(a);
    d.add_undirected_edge(a, b, 1);
  }
  vector<long long> p = d.shortest_path(0);
  for (long long i = 0; i < n; i++) {
    if (ma < p[i]) {
      ma = p[i];
      l = i;
    }
  }
  ma = 0;
  L = d.shortest_path(l);
  for (long long i = 0; i < n; i++) {
    if (ma < L[i]) {
      ma = L[i];
      r = i;
    }
  }
  R = d.shortest_path(r);
  dfs(l);
  for (long long i = 0; i < n; i++) used[i] = false;
  dfs2(l);
  cout << sum << endl;
  for (auto i : ans) {
    cout << i[0] + 1 << " " << i[1] + 1 << " " << i[2] + 1 << "\n";
  }
}

```