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;
const long long MAXN = 200100;
long long p1, p2, n, ans, niv[MAXN], ordem[MAXN], distp1[MAXN], distp2[MAXN];
vector<long long> graph[MAXN], path, diam, atp;
bool pro[MAXN], mark[MAXN];
void ponta1(long long x) {
  pro[x] = true;
  for (auto u : graph[x]) {
    if (pro[u]) continue;
    niv[u] = niv[x] + 1;
    if (niv[u] > niv[p1]) p1 = u;
    ponta1(u);
  }
  p1 = p1 == 0 ? x : p1;
}
void ponta2(long long x) {
  pro[x] = true;
  for (auto u : graph[x]) {
    if (pro[u]) continue;
    niv[u] = niv[x] + 1;
    if (niv[u] > niv[p2]) p2 = u;
    ponta2(u);
  }
  p2 = (p2 == 0 ? x : p2);
}
void caminho(long long v, long long t, long long p) {
  if (path.size() > 0) return;
  atp.push_back(v);
  if (v == t) path = atp;
  for (auto u : graph[v])
    if (u != p) caminho(u, t, v);
  atp.pop_back();
}
vector<long long> diametro(long long x) {
  memset(pro, false, sizeof pro);
  p1 = p2 = 0;
  ponta1(x);
  memset(pro, false, sizeof pro);
  ponta2(p1);
  vector<long long> r;
  path.clear();
  caminho(p1, p2, -1);
  r = path;
  return r;
}
void defniv(long long x) {
  for (auto u : graph[x]) {
    if (mark[u] || (ordem[u] < ordem[x] && ordem[u] != 0)) continue;
    ordem[u] = ordem[x] + 1;
    defniv(u);
  }
}
void calcp1(long long x = p1) {
  for (auto u : graph[x]) {
    if (distp1[u] != 0) continue;
    distp1[u] = distp1[x] + 1 + (x == p1 ? 1 : 0);
    calcp1(u);
  }
}
void calcp2(long long x = p2) {
  for (auto u : graph[x]) {
    if (distp2[u] != 0) continue;
    distp2[u] = distp2[x] + 1 + (x == p2 ? 1 : 0);
    calcp2(u);
  }
}
signed main() {
  scanf("%lld", &n);
  for (long long i = 1, a, b; i < n; i++)
    scanf("%lld %lld", &a, &b), graph[a].push_back(b), graph[b].push_back(a);
  diam = diametro(1);
  distp1[p1] = distp2[p2] = -1;
  calcp1(), calcp2();
  for (long long i = 0; i < diam.size(); i++)
    mark[diam[i]] = 1, ordem[diam[i]] = 0;
  for (long long i = 0; i < diam.size(); i++) defniv(diam[i]);
  vector<pair<long long, pair<long long, long long>>> resp;
  for (long long i = 1, r1, r2; i <= n; i++) {
    if (!mark[i]) {
      r1 = distp1[i];
      r2 = distp2[i];
      if (r1 > r2)
        resp.push_back({ordem[i], {i, p1}});
      else
        resp.push_back({ordem[i], {i, p2}});
      ans += max(r1, r2);
    }
  }
  printf("%lld\n", ans + (((long long)diam.size()) * 1LL *
                          ((long long)diam.size() - 1LL) / 2LL));
  sort(resp.begin(), resp.end()), reverse(resp.begin(), resp.end());
  for (auto u : resp)
    printf("%lld %lld %lld\n", u.second.first, u.second.second, u.second.first);
  for (long long i = 0; i < diam.size() - 1; i++)
    printf("%lld %lld %lld\n", diam[i], diam[diam.size() - 1], diam[i]);
}