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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
constexpr int MAXN = 2 * 100000 + 4;
int n;
vi gr[MAXN];
vi bfs(int sv) {
  vi vd(n + 1, -1);
  queue<int> vq;
  vq.push(sv);
  vd[sv] = 0;
  int numv = 0;
  while (numv < n) {
    int cv = vq.front();
    vq.pop();
    ++numv;
    for (auto nv : gr[cv]) {
      if (vd[nv] == -1) {
        vd[nv] = vd[cv] + 1;
        vq.push(nv);
      }
    }
  }
  return vd;
}
vi fd(const vi& d) {
  int rv = distance(d.begin(), max_element(d.begin(), d.end()));
  vi diam;
  while (d[rv] > 0) {
    diam.push_back(rv);
    for (auto nv : gr[rv]) {
      if (d[nv] + 1 == d[rv]) {
        rv = nv;
        break;
      }
    }
  }
  diam.push_back(rv);
  return diam;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int f, t;
    cin >> f >> t;
    gr[f].push_back(t);
    gr[t].push_back(f);
  }
  vi d = bfs(1);
  int rv1 = distance(d.begin(), max_element(d.begin(), d.end()));
  vi d1 = bfs(rv1);
  int rv2 = distance(d1.begin(), max_element(d1.begin(), d1.end()));
  vi d2 = bfs(rv2);
  vi diam = fd(d1);
  set<int> ds(diam.begin(), diam.end());
  vi ind(n);
  iota(ind.begin(), ind.end(), 1);
  sort(ind.begin(), ind.end(),
       [&](int l, int r) { return max(d1[l], d2[l]) > max(d1[r], d2[r]); });
  ull res = 0;
  vector<tuple<int, int, int>> a;
  for (auto v : ind) {
    if (ds.find(v) == ds.end()) {
      if (d1[v] > d2[v]) {
        a.push_back(make_tuple(rv1, v, v));
        res += d1[v];
      } else {
        a.push_back(make_tuple(rv2, v, v));
        res += d2[v];
      }
    }
  }
  for (int i = 0; i + 1 < (int)diam.size(); ++i) {
    a.push_back(make_tuple(diam[i], diam.back(), diam[i]));
  }
  res += ((ull)ds.size() - 1) * (ull)ds.size() / 2;
  cout << res << endl;
  for (auto t : a) {
    cout << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << endl;
  }
  return 0;
}