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;
struct node {
  int front, nex;
} graph[600001];
int tail = 200000;
int dis[200001], dis2[200001];
bool vis[200001];
int p, p2, v, from, to, tmp1, tmp2;
long long ans = 0;
int parent[200001];
bool onpath[200001];
int output[200001][3];
int noutput = 0;
inline void read(int &x) {
  x = 0;
  char ch = getchar();
  bool f = 0;
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (((x << 2) + x) << 1) + ch - 48;
    ch = getchar();
  }
  if (f) x = -x;
}
void bfs(int x) {
  memset(vis, 0, sizeof(vis));
  queue<int> q;
  q.push(x);
  while (!q.empty()) {
    int now = q.front();
    vis[now] = true;
    p = now;
    q.pop();
    for (int i = graph[now].nex; i; i = graph[i].nex) {
      if (!vis[graph[i].front]) {
        dis[graph[i].front] = dis[now] + 1;
        q.push(graph[i].front);
      }
    }
  }
}
void bfs2(int x) {
  memset(vis, 0, sizeof(vis));
  queue<int> q;
  q.push(x);
  while (!q.empty()) {
    int now = q.front();
    p2 = now;
    vis[now] = true;
    q.pop();
    for (int i = graph[now].nex; i; i = graph[i].nex) {
      if (!vis[graph[i].front]) {
        parent[graph[i].front] = now;
        dis2[graph[i].front] = dis2[now] + 1;
        q.push(graph[i].front);
      }
    }
  }
}
void dfs(int now) {
  vis[now] = true;
  for (int i = graph[now].nex; i; i = graph[i].nex) {
    if (!vis[graph[i].front]) {
      dfs(graph[i].front);
    }
  }
  if (!onpath[now]) {
    if (dis[now] > dis2[now]) {
      ans += dis[now];
      output[noutput][0] = output[noutput][2] = now;
      output[noutput++][1] = p2;
    } else {
      ans += dis2[now];
      output[noutput][0] = output[noutput][2] = now;
      output[noutput++][1] = p;
    }
  }
}
int main() {
  read(v);
  for (int i = 1; i < v; i++) {
    read(from);
    read(to);
    tmp1 = graph[from].nex;
    tmp2 = graph[to].nex;
    graph[from].nex = ++tail;
    graph[to].nex = ++tail;
    graph[tail - 1].front = to;
    graph[tail].front = from;
    graph[tail - 1].nex = tmp1;
    graph[tail].nex = tmp2;
  }
  bfs(1);
  dis[p] = 0;
  bfs(p);
  bfs2(p);
  for (int i = p2; i != p; i = parent[i]) {
    ans += dis2[i];
    onpath[i] = true;
  }
  onpath[p] = true;
  memset(vis, 0, sizeof(vis));
  dfs(p);
  cout << ans << endl;
  for (int i = 0; i < noutput; i++) {
    printf("%d %d %d\n", output[i][0], output[i][1], output[i][2]);
  }
  for (int i = p2; i != p; i = parent[i]) {
    printf("%d %d %d\n", i, p, i);
  }
  return 0;
}