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>
const int MAXN = 2e5;
int n, edge, ans1, lu, lv;
int f[MAXN | 1], fst[MAXN | 1], depth[MAXN | 1], father[MAXN | 1];
int calc[MAXN][2];
bool vis[MAXN | 1], flag[MAXN | 1];
long long ans;
int dp[MAXN | 1];
std::vector<int> vec[2];
struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN << 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void add_edge(int x, int y) {
  e[++edge] = Edge(x, y);
  fst[x] = edge;
}
void dfs1(int x, int fa) {
  father[x] = fa;
  depth[x] = depth[fa] + 1;
  dp[x] = 1;
  f[x] = x;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs1(to, x);
    if (dp[to] + dp[x] > ans) {
      ans = dp[x] + dp[to];
      lu = f[x];
      lv = f[to];
    }
    if (dp[to] + 1 > dp[x]) {
      dp[x] = dp[to] + 1;
      f[x] = f[to];
    }
  }
}
void dfs2(int x, int dis, int fa, int from) {
  if (!vis[x]) {
    if (dis > calc[x][0]) {
      calc[x][0] = dis;
      calc[x][1] = from;
    }
    if (from == lv) ans += calc[x][0];
  }
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs2(to, dis + 1, x, from);
  }
}
void dfs3(int x) {
  flag[x] = 1;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (vis[to] || flag[to]) continue;
    dfs3(to);
  }
  if (!vis[x]) {
    printf("%d %d %d\n", x, calc[x][1], x);
  }
}
int main() {
  n = read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs1(1, 0);
  ans = ans * (ans - 1) / 2;
  int tx = lu, ty = lv;
  if (depth[tx] < depth[ty]) std::swap(tx, ty);
  while (depth[tx] > depth[ty])
    vis[tx] = 1, vec[0].push_back(tx), tx = father[tx];
  while (tx != ty)
    vis[tx] = 1, vis[ty] = 1, vec[0].push_back(tx), vec[1].push_back(ty),
    tx = father[tx], ty = father[ty];
  vis[tx] = 1;
  vec[0].push_back(tx);
  for (int i = vec[1].size() - 1; i >= 0; --i) vec[0].push_back(vec[1][i]);
  vec[1].clear();
  dfs2(lu, 0, 0, lu);
  dfs2(lv, 0, 0, lv);
  printf("%lld\n", ans);
  for (std::vector<int>::iterator it = vec[0].begin(); it != vec[0].end();
       ++it) {
    int now = *it;
    dfs3(now);
  }
  for (int i = 0; i < vec[0].size() - 1; ++i) {
    printf("%d %d %d\n", vec[0][i], vec[0][vec[0].size() - 1], vec[0][i]);
  }
  return 0;
}