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>
struct edge {
  int to, nxt;
} E[500000];
int H[300000], tot;
void add_edge(int a, int b) {
  E[++tot] = (edge){b, H[a]};
  H[a] = tot;
  E[++tot] = (edge){a, H[b]};
  H[b] = tot;
}
int Fa[300000], son[300000];
int dep[300000];
int root, rroot;
int dfs(int now, int fa, int dep) {
  Fa[now] = fa;
  ::dep[now] = dep;
  if (dep > ::dep[root]) root = now;
  int depth = 0;
  for (int i = H[now]; i; i = E[i].nxt) {
    if (E[i].to == fa) continue;
    int nxt = dfs(E[i].to, now, dep + 1);
    if (nxt + 1 > depth) depth = nxt + 1, son[now] = E[i].to;
  }
  return depth;
}
int n;
int x, y, With;
long long ans;
int buf[300000][3], buftot;
void solve(int now, int fa, int dep, int ext = 0) {
  for (int i = H[now]; i; i = E[i].nxt) {
    if (E[i].to == fa || E[i].to == ext) continue;
    solve(E[i].to, now, dep + 1);
  }
  if (!ext && now != rroot) {
    ans += dep;
    buftot++;
    buf[buftot][0] = buf[buftot][2] = now;
    buf[buftot][1] = With;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y);
  }
  dfs(1, 0, 0);
  rroot = root;
  memset(dep, 0, sizeof(dep));
  dfs(root, 0, 0);
  std::swap(rroot, root);
  for (int now = rroot; now != root; now = Fa[now]) {
    With = (dep[now] > dep[rroot] - dep[now]) ? root : rroot;
    solve(now, Fa[now], abs(dep[With] - dep[now]), son[now]);
  }
  for (int now = rroot; now != root; now = Fa[now]) {
    ans += dep[now];
    buftot++;
    buf[buftot][0] = buf[buftot][2] = now;
    buf[buftot][1] = root;
  }
  printf("%I64d\n", ans);
  for (int i = 1; i <= buftot; i++)
    printf("%d %d %d\n", buf[i][0], buf[i][1], buf[i][2]);
}