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;
const int inf = 1 << 30;
const long long INF = 1LL << 60;
const int MaxN = 200000;
int n, diaL, diaR, all;
int pre[2 * MaxN + 5], last[MaxN + 5], other[2 * MaxN + 5];
int dep[MaxN + 5], dis[MaxN + 5], ind[MaxN + 5];
int up[MaxN + 5][22];
bool is_dia[MaxN + 5];
long long res;
vector<int> diameter;
struct Ask {
  int u, v, del;
  Ask() {}
  Ask(int _u, int _v, int _del) {
    u = _u;
    v = _v;
    del = _del;
  }
};
vector<Ask> ans;
void build(int x, int y) {
  pre[++all] = last[x];
  last[x] = all;
  other[all] = y;
}
void Dfs(int x, int fa) {
  dep[x] = dep[fa] + 1;
  up[x][0] = fa;
  for (int i = 1; i <= 20; i++) up[x][i] = up[up[x][i - 1]][i - 1];
  for (int ed = last[x]; ed != -1; ed = pre[ed]) {
    int dr = other[ed];
    if (dr != fa) {
      Dfs(dr, x);
      ind[x]++;
    }
  }
}
int Get_LCA(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int d = dep[x] - dep[y];
  for (int i = 0; i <= 20; i++)
    if (d & (1 << i)) x = up[x][i];
  if (x == y) return x;
  for (int i = 20; i >= 0; i--) {
    if (up[x][i] != up[y][i]) {
      x = up[x][i];
      y = up[y][i];
    }
  }
  return up[x][0];
}
int get_dist(int x, int y) {
  int u = Get_LCA(x, y);
  return dep[x] + dep[y] - 2 * dep[u];
}
void dia_Dfs(int x, int fa) {
  dis[x] = dis[fa] + 1;
  for (int ed = last[x]; ed != -1; ed = pre[ed]) {
    int dr = other[ed];
    if (dr != fa) dia_Dfs(dr, x);
  }
}
void Get_diameter() {
  dia_Dfs(1, 0);
  int MAX = 0;
  for (int i = 1; i <= n; i++) {
    if (dis[i] > MAX) {
      MAX = dis[i];
      diaL = i;
    }
  }
  memset(dis, 0, sizeof(dis));
  dia_Dfs(diaL, 0);
  MAX = 0;
  for (int i = 1; i <= n; i++) {
    if (dis[i] > MAX) {
      MAX = dis[i];
      diaR = i;
    }
  }
}
void mark_diameter() {
  int now = diaR;
  while (now != diaL) {
    diameter.push_back(now);
    is_dia[now] = true;
    now = up[now][0];
  }
  diameter.push_back(diaL);
  is_dia[diaL] = true;
}
void del_not_diameter() {
  queue<int> Q;
  for (int i = 1; i <= n; i++)
    if (ind[i] == 0 && !is_dia[i]) Q.push(i);
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    int lx = get_dist(cur, diaL);
    int ly = get_dist(cur, diaR);
    res += 1LL * max(lx, ly);
    if (lx > ly)
      ans.push_back(Ask(cur, diaL, cur));
    else
      ans.push_back(Ask(cur, diaR, cur));
    int father = up[cur][0];
    ind[father]--;
    if (!is_dia[father] && ind[father] == 0) Q.push(father);
  }
}
void del_diameter() {
  int tmp = (int)diameter.size();
  res += 1LL * tmp * (tmp - 1) / 2LL;
  for (int i = 0; i < diameter.size() - 1; i++)
    ans.push_back(Ask(diameter[i], diaL, diameter[i]));
}
void solve() {
  res = 0LL;
  ans.clear();
  diameter.clear();
  memset(is_dia, 0, sizeof(is_dia));
  mark_diameter();
  del_not_diameter();
  del_diameter();
  cout << res << endl;
  for (int i = 0; i < ans.size(); i++)
    printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].del);
}
int main() {
  while (scanf("%d", &n) != EOF) {
    all = -1;
    memset(last, -1, sizeof(last));
    for (int i = 1; i < n; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      build(u, v);
      build(v, u);
    }
    Get_diameter();
    Dfs(diaL, 0);
    solve();
  }
  return 0;
}