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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int head[404040], nxt[404040], to[404040], L[404040], deep[404040], mx[404040];
int E, N, M, pa[404040], qq[404040], dist[2][404040], qf, qb, vst[404040];
pair<int, int> p[404040];
vector<pair<pair<int, int>, int> > T;
void add(int u, int v) {
  to[E] = v, nxt[E] = head[u], head[u] = E++;
  to[E] = u, nxt[E] = head[v], head[v] = E++;
}
void dfs(int u) {
  pair<int, int> q;
  mx[u] = u, L[u] = -1;
  int m1 = u, m2 = 0;
  for (int e = head[u]; ~e; e = nxt[e]) {
    int v = to[e];
    if (deep[v] >= 0) continue;
    deep[v] = deep[u] + 1, pa[v] = u;
    dfs(v);
    if (deep[mx[v]] > deep[m2]) m2 = mx[v];
    if (deep[m2] > deep[m1]) swap(m1, m2);
    if (L[u] < L[v]) L[u] = L[v], q = p[v];
  }
  if (m2 && L[u] < deep[m1] + deep[m2] - deep[u] * 2)
    L[u] = deep[m1] + deep[m2] - deep[u] * 2, q = make_pair(m1, m2);
  p[u] = q, mx[u] = m1;
}
void DFS(int u, int k) {
  for (int e = head[u]; ~e; e = nxt[e]) {
    int v = to[e];
    if (dist[k][v] >= 0) continue;
    dist[k][v] = dist[k][u] + 1;
    if (k == 1 && dist[0][v] + dist[1][v] == L[1])
      T.push_back(make_pair(make_pair(p[1].second, v), v));
    DFS(v, k);
  }
}
int main() {
  int u, v;
  cin >> N;
  memset(mx, -1, sizeof mx);
  memset(head, -1, sizeof head);
  memset(deep, -1, sizeof deep);
  memset(dist, -1, sizeof dist);
  for (int i = 1; i < N; i++) gn(u, v), add(u, v);
  deep[1] = 0;
  dfs(1);
  dist[0][p[1].first] = 0, dist[1][p[1].second] = 0;
  DFS(p[1].first, 0);
  DFS(p[1].second, 1);
  for (int i = 1; i <= N; i++)
    if (dist[0][i] + dist[1][i] == L[1]) {
      vst[i] = 1;
      qq[qb++] = i;
    }
  long long ans = 1LL * L[1] * (L[1] + 1) / 2;
  while (qf < qb) {
    int u = qq[qf++];
    for (int e = head[u]; ~e; e = nxt[e]) {
      int v = to[e];
      if (vst[v]) continue;
      vst[v] = 1;
      qq[qb++] = v;
      if (dist[0][v] > dist[1][v])
        T.push_back(make_pair(make_pair(p[1].first, v), v));
      else
        T.push_back(make_pair(make_pair(p[1].second, v), v));
      ans += max(dist[0][v], dist[1][v]);
    }
  }
  println(ans);
  reverse(T.begin(), T.end());
  for (int i = 0; i < T.size(); i++) {
    printf("%d %d %d\n", T[i].first.first, T[i].first.second, T[i].second);
  }
  return 0;
}