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;
long long a, b, c, d, e, i, j, ii, jj, zx, xc, qw[200009], we[200009], pas, pi,
    k[200009];
pair<pair<long long, long long>, long long> p[600009];
bool bo[200009], rko[200009];
vector<long long> v[200009];
deque<long long> de;
void dfsst(long long q, long long w, long long rr) {
  if (rr > xc) {
    xc = rr;
    zx = q;
  }
  for (vector<long long>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    dfsst((*it), q, rr + 1);
  }
}
void dfsst2(long long q, long long w, long long rr) {
  if (rr > xc) {
    xc = rr;
    zx = q;
  }
  for (vector<long long>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    dfsst2((*it), q, rr + 1);
  }
}
void dfs(long long q, long long w, long long rr) {
  qw[q] = rr - 1;
  for (vector<long long>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    dfs((*it), q, rr + 1);
  }
}
void dfs2(long long q, long long w, long long rr) {
  if (d == 0) bo[q] = 1;
  if (q == e) d = 1;
  we[q] = rr - 1;
  for (vector<long long>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    dfs2((*it), q, rr + 1);
  }
  if (d == 0) bo[q] = 0;
}
void dfs3(long long q, long long w) {
  if (q == zx) return;
  pi++;
  p[pi].first.first = q;
  p[pi].first.second = zx;
  p[pi].second = q;
  for (vector<long long>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    if (bo[(*it)] == 1) {
      dfs3((*it), q);
      return;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> a;
  for (i = 1; i < a; i++) {
    cin >> c >> d;
    v[c].push_back(d);
    v[d].push_back(c);
    k[c]++;
    k[d]++;
  }
  zx = 0;
  xc = 0;
  dfsst(1, 0, 1);
  e = zx;
  zx = 0;
  xc = 0;
  dfsst2(e, 0, 1);
  dfs(e, 0, 1);
  d = 0;
  dfs2(zx, 0, 1);
  for (i = 1; i <= a; i++) {
    if (bo[i] == 0 && v[i].size() == 1) {
      de.push_back(i);
      rko[i] = 1;
    }
  }
  while (de.size() != 0) {
    c = de.front();
    de.pop_front();
    pas += max(qw[c], we[c]);
    pi++;
    if (qw[c] >= we[c]) {
      p[pi].first.first = e;
      p[pi].first.second = c;
      p[pi].second = c;
    } else {
      p[pi].first.first = zx;
      p[pi].first.second = c;
      p[pi].second = c;
    }
    d = 0;
    for (vector<long long>::iterator it = v[c].begin(); it != v[c].end();
         it++) {
      if (rko[(*it)] == 1) continue;
      d = (*it);
      break;
    }
    k[d]--;
    if (d != 0 && bo[d] == 0 && k[d] == 1) {
      de.push_back(d);
      rko[d] = 1;
    }
  }
  pas += qw[zx] * (qw[zx] + 1) / 2;
  dfs3(e, 0);
  cout << pas << endl;
  for (i = 1; i <= pi; i++)
    cout << p[i].first.first << " " << p[i].first.second << " " << p[i].second
         << endl;
  return 0;
}