#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll inf = 1000000000;
constexpr ll mod = 1000000007;
constexpr long double eps = 1e-6;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << to_string(p.first) << " " << to_string(p.second);
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (ll i = (0); i < (ll)(v.size()); i++) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
struct modint {
  ll n;

 public:
  modint(const ll n = 0) : n((n % mod + mod) % mod) {}
  static modint pow(modint a, int m) {
    modint r = 1;
    while (m > 0) {
      if (m & 1) {
        r *= a;
      }
      a = (a * a);
      m /= 2;
    }
    return r;
  }
  modint& operator++() {
    *this += 1;
    return *this;
  }
  modint& operator--() {
    *this -= 1;
    return *this;
  }
  modint operator++(int) {
    modint ret = *this;
    *this += 1;
    return ret;
  }
  modint operator--(int) {
    modint ret = *this;
    *this -= 1;
    return ret;
  }
  modint operator~() const { return (this->pow(n, mod - 2)); }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.n == rhs.n;
  }
  friend bool operator<(const modint& lhs, const modint& rhs) {
    return lhs.n < rhs.n;
  }
  friend bool operator>(const modint& lhs, const modint& rhs) {
    return lhs.n > rhs.n;
  }
  friend modint& operator+=(modint& lhs, const modint& rhs) {
    lhs.n += rhs.n;
    if (lhs.n >= mod) lhs.n -= mod;
    return lhs;
  }
  friend modint& operator-=(modint& lhs, const modint& rhs) {
    lhs.n -= rhs.n;
    if (lhs.n < 0) lhs.n += mod;
    return lhs;
  }
  friend modint& operator*=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * rhs.n) % mod;
    return lhs;
  }
  friend modint& operator/=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * (~rhs).n) % mod;
    return lhs;
  }
  friend modint operator+(const modint& lhs, const modint& rhs) {
    return modint(lhs.n + rhs.n);
  }
  friend modint operator-(const modint& lhs, const modint& rhs) {
    return modint(lhs.n - rhs.n);
  }
  friend modint operator*(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * rhs.n);
  }
  friend modint operator/(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * (~rhs).n);
  }
};
istream& operator>>(istream& is, modint m) {
  is >> m.n;
  return is;
}
ostream& operator<<(ostream& os, modint m) {
  os << m.n;
  return os;
}
long long extgcd(long long a, long long b, long long& x, long long& y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
long long mod_inverse(long long a, long long m) {
  long long x, y;
  if (extgcd(a, m, x, y) == 1)
    return (m + x % m) % m;
  else
    return -1;
}
vector<long long> fact(1010101 + 1, inf);
long long mod_fact(long long n, long long& e) {
  if (fact[0] == inf) {
    fact[0] = 1;
    if (1010101 != 0) fact[1] = 1;
    for (ll i = 2; i <= 1010101; ++i) {
      fact[i] = (fact[i - 1] * i) % mod;
    }
  }
  e = 0;
  if (n == 0) return 1;
  long long res = mod_fact(n / mod, e);
  e += n / mod;
  if ((n / mod) % 2 != 0) return (res * (mod - fact[n % mod])) % mod;
  return (res * fact[n % mod]) % mod;
}
long long mod_comb(long long n, long long k) {
  if (n < 0 || k < 0 || n < k) return 0;
  long long e1, e2, e3;
  long long a1 = mod_fact(n, e1), a2 = mod_fact(k, e2),
            a3 = mod_fact(n - k, e3);
  if (e1 > e2 + e3) return 0;
  return (a1 * mod_inverse((a2 * a3) % mod, mod)) % mod;
}
using mi = modint;
mi mod_pow(mi a, ll n) {
  mi ret = 1;
  mi tmp = a;
  while (n > 0) {
    if (n % 2) ret *= tmp;
    tmp = tmp * tmp;
    n /= 2;
  }
  return ret;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
using ld = long double;
using vertex = int;
using graph = vector<vector<vertex>>;
pair<int, vertex> farest(graph& g, vertex v, vertex par = -1, int dist = 0) {
  pair<int, vertex> ret = {dist, v};
  for (auto child : g[v])
    if (child != par) {
      ret = max(ret, farest(g, child, v, dist + 1));
    }
  return ret;
}
int diameter(graph& g, pair<vertex, vertex>& ends, vertex v = 0,
             bool isTwice = false) {
  auto [diam, u] = farest(g, v);
  if (!isTwice) return diameter(g, ends, u, true);
  ends.first = v;
  ends.second = u;
  return diam;
}
vector<vector<int>> dist;
void dfs(graph& g, int v, int type, int par = -1, int d = 0) {
  dist[type][v] = d;
  for (auto adj : g[v]) {
    if (adj == par) continue;
    dfs(g, adj, type, v, d + 1);
  }
  return;
}
ll ans_val = 0;
vector<pair<vertex, vertex>> ans_pair;
vector<vertex> ans_erased;
pair<vertex, vertex> endss;
ll diam = 0;
void build_ans(graph& g, vertex v, bool onDiam, vertex par = -1) {
  int last = -1;
  for (auto adj : g[v]) {
    if (adj == par) continue;
    if (onDiam && dist[0][adj] + dist[1][adj] == diam)
      last = adj;
    else
      build_ans(g, adj, false, v);
  }
  if (last != -1) build_ans(g, last, true, v);
  if (!onDiam) {
    if (dist[0][v] >= dist[1][v]) {
      ans_val += dist[0][v];
      ans_pair.push_back({v + 1, endss.first + 1});
      ans_erased.push_back(v + 1);
    } else {
      ans_val += dist[1][v];
      ans_pair.push_back({v + 1, endss.second + 1});
      ans_erased.push_back(v + 1);
    }
  } else if (v != endss.first) {
    ans_val += dist[0][v];
    ans_pair.push_back({v + 1, endss.first + 1});
    ans_erased.push_back(v + 1);
  }
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  graph g(n);
  dist.resize(2, vector<int>(n, 0));
  for (ll i = (0); i < (ll)(n - 1); i++) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  diam = diameter(g, endss);
  dfs(g, endss.first, 0);
  dfs(g, endss.second, 1);
  build_ans(g, endss.first, true);
  cout << ans_val << endl;
  for (ll i = (0); i < (ll)(n - 1); i++) {
    cout << ans_pair[i].first << " " << ans_pair[i].second << " "
         << ans_erased[i] << "\n";
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll inf = 1000000000;
constexpr ll mod = 1000000007;
constexpr long double eps = 1e-6;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << to_string(p.first) << " " << to_string(p.second);
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (ll i = (0); i < (ll)(v.size()); i++) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
struct modint {
  ll n;

 public:
  modint(const ll n = 0) : n((n % mod + mod) % mod) {}
  static modint pow(modint a, int m) {
    modint r = 1;
    while (m > 0) {
      if (m & 1) {
        r *= a;
      }
      a = (a * a);
      m /= 2;
    }
    return r;
  }
  modint& operator++() {
    *this += 1;
    return *this;
  }
  modint& operator--() {
    *this -= 1;
    return *this;
  }
  modint operator++(int) {
    modint ret = *this;
    *this += 1;
    return ret;
  }
  modint operator--(int) {
    modint ret = *this;
    *this -= 1;
    return ret;
  }
  modint operator~() const { return (this->pow(n, mod - 2)); }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.n == rhs.n;
  }
  friend bool operator<(const modint& lhs, const modint& rhs) {
    return lhs.n < rhs.n;
  }
  friend bool operator>(const modint& lhs, const modint& rhs) {
    return lhs.n > rhs.n;
  }
  friend modint& operator+=(modint& lhs, const modint& rhs) {
    lhs.n += rhs.n;
    if (lhs.n >= mod) lhs.n -= mod;
    return lhs;
  }
  friend modint& operator-=(modint& lhs, const modint& rhs) {
    lhs.n -= rhs.n;
    if (lhs.n < 0) lhs.n += mod;
    return lhs;
  }
  friend modint& operator*=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * rhs.n) % mod;
    return lhs;
  }
  friend modint& operator/=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * (~rhs).n) % mod;
    return lhs;
  }
  friend modint operator+(const modint& lhs, const modint& rhs) {
    return modint(lhs.n + rhs.n);
  }
  friend modint operator-(const modint& lhs, const modint& rhs) {
    return modint(lhs.n - rhs.n);
  }
  friend modint operator*(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * rhs.n);
  }
  friend modint operator/(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * (~rhs).n);
  }
};
istream& operator>>(istream& is, modint m) {
  is >> m.n;
  return is;
}
ostream& operator<<(ostream& os, modint m) {
  os << m.n;
  return os;
}
long long extgcd(long long a, long long b, long long& x, long long& y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
long long mod_inverse(long long a, long long m) {
  long long x, y;
  if (extgcd(a, m, x, y) == 1)
    return (m + x % m) % m;
  else
    return -1;
}
vector<long long> fact(1010101 + 1, inf);
long long mod_fact(long long n, long long& e) {
  if (fact[0] == inf) {
    fact[0] = 1;
    if (1010101 != 0) fact[1] = 1;
    for (ll i = 2; i <= 1010101; ++i) {
      fact[i] = (fact[i - 1] * i) % mod;
    }
  }
  e = 0;
  if (n == 0) return 1;
  long long res = mod_fact(n / mod, e);
  e += n / mod;
  if ((n / mod) % 2 != 0) return (res * (mod - fact[n % mod])) % mod;
  return (res * fact[n % mod]) % mod;
}
long long mod_comb(long long n, long long k) {
  if (n < 0 || k < 0 || n < k) return 0;
  long long e1, e2, e3;
  long long a1 = mod_fact(n, e1), a2 = mod_fact(k, e2),
            a3 = mod_fact(n - k, e3);
  if (e1 > e2 + e3) return 0;
  return (a1 * mod_inverse((a2 * a3) % mod, mod)) % mod;
}
using mi = modint;
mi mod_pow(mi a, ll n) {
  mi ret = 1;
  mi tmp = a;
  while (n > 0) {
    if (n % 2) ret *= tmp;
    tmp = tmp * tmp;
    n /= 2;
  }
  return ret;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
using ld = long double;
using vertex = int;
using graph = vector<vector<vertex>>;
pair<int, vertex> farest(graph& g, vertex v, vertex par = -1, int dist = 0) {
  pair<int, vertex> ret = {dist, v};
  for (auto child : g[v])
    if (child != par) {
      ret = max(ret, farest(g, child, v, dist + 1));
    }
  return ret;
}
int diameter(graph& g, pair<vertex, vertex>& ends, vertex v = 0,
             bool isTwice = false) {
  auto [diam, u] = farest(g, v);
  if (!isTwice) return diameter(g, ends, u, true);
  ends.first = v;
  ends.second = u;
  return diam;
}
vector<vector<int>> dist;
void dfs(graph& g, int v, int type, int par = -1, int d = 0) {
  dist[type][v] = d;
  for (auto adj : g[v]) {
    if (adj == par) continue;
    dfs(g, adj, type, v, d + 1);
  }
  return;
}
ll ans_val = 0;
vector<pair<vertex, vertex>> ans_pair;
vector<vertex> ans_erased;
pair<vertex, vertex> endss;
ll diam = 0;
void build_ans(graph& g, vertex v, bool onDiam, vertex par = -1) {
  int last = -1;
  for (auto adj : g[v]) {
    if (adj == par) continue;
    if (onDiam && dist[0][adj] + dist[1][adj] == diam)
      last = adj;
    else
      build_ans(g, adj, false, v);
  }
  if (last != -1) build_ans(g, last, true, v);
  if (!onDiam) {
    if (dist[0][v] >= dist[1][v]) {
      ans_val += dist[0][v];
      ans_pair.push_back({v + 1, endss.first + 1});
      ans_erased.push_back(v + 1);
    } else {
      ans_val += dist[1][v];
      ans_pair.push_back({v + 1, endss.second + 1});
      ans_erased.push_back(v + 1);
    }
  } else if (v != endss.first) {
    ans_val += dist[0][v];
    ans_pair.push_back({v + 1, endss.first + 1});
    ans_erased.push_back(v + 1);
  }
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  graph g(n);
  dist.resize(2, vector<int>(n, 0));
  for (ll i = (0); i < (ll)(n - 1); i++) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  diam = diameter(g, endss);
  dfs(g, endss.first, 0);
  dfs(g, endss.second, 1);
  build_ans(g, endss.first, true);
  cout << ans_val << endl;
  for (ll i = (0); i < (ll)(n - 1); i++) {
    cout << ans_pair[i].first << " " << ans_pair[i].second << " "
         << ans_erased[i] << "\n";
  }
  return 0;
}

```