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;
int depth[200005];
int depth2[200005];
struct edge {
  int y;
  edge* next;
};
edge* li[200005];
edge* new_edge() {
  static edge a[400005];
  static int top = 0;
  return &a[top++];
}
void inserts(int x, int y) {
  edge* t = new_edge();
  t->y = y;
  t->next = li[x];
  li[x] = t;
}
void insert_edge(int x, int y) {
  inserts(x, y);
  inserts(y, x);
}
bool protecteds[200005];
void dfs(int x, int fa = -1) {
  edge* t;
  for (t = li[x]; t != 0; t = t->next) {
    if (t->y == fa) continue;
    depth[t->y] = depth[x] + 1;
    dfs(t->y, x);
  }
}
void dfs2(int x, int fa = -1) {
  edge* t;
  for (t = li[x]; t != 0; t = t->next) {
    if (t->y == fa) continue;
    depth2[t->y] = depth2[x] + 1;
    dfs2(t->y, x);
  }
}
int now, end2;
long long ans = 0;
bool vis[200005];
void dfs3(int x) {
  bool tag = false;
  if (protecteds[x]) tag = true;
  protecteds[x] = true;
  vis[x] = true;
  edge* t;
  for (t = li[x]; t != 0; t = t->next) {
    if (protecteds[t->y]) continue;
    dfs3(t->y);
  }
  if (tag) return;
  if (depth[x] > depth2[x]) {
    printf("%d %d %d\n", now + 1, x + 1, x + 1);
    ans += depth[x];
  } else {
    printf("%d %d %d\n", end2 + 1, x + 1, x + 1);
    ans += depth2[x];
  }
  protecteds[x] = false;
}
void dfs4(int x, int fa = -1) {
  edge* t;
  for (t = li[x]; t != 0; t = t->next) {
    if (t->y == fa) continue;
    if (!protecteds[t->y]) continue;
    dfs4(t->y, x);
  }
  if (x != now) {
    printf("%d %d %d\n", now + 1, x + 1, x + 1);
    ans += depth[x];
  }
}
int main() {
  int n;
  scanf("%d", &n);
  int i;
  for (i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    insert_edge(x, y);
  }
  depth[0] = 0;
  dfs(0);
  now = 0;
  for (i = 0; i < n; i++) {
    if (depth[i] > depth[now]) {
      now = i;
    }
  }
  depth[now] = 0;
  dfs(now);
  end2 = now;
  for (i = 0; i < n; i++) {
    if (depth[i] > depth[end2]) {
      end2 = i;
    }
  }
  dfs2(end2);
  for (i = 0; i < n; i++) {
    if (depth[i] + depth2[i] == depth[end2]) {
      protecteds[i] = true;
      ans += depth[i];
    } else {
      ans += max(depth[i], depth2[i]);
    }
  }
  cout << ans << endl;
  for (i = 0; i < n; i++) {
    if (protecteds[i]) {
      dfs3(i);
    }
  }
  dfs4(now);
  return 0;
}