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 N = 2e5 + 20, LG = 20;
long long n, par[N][LG], h[N], hv[N], U, V, sum;
vector<int> gr[N];
bool vis[N], seen[N];
vector<pair<pair<int, int>, int>> ans;
void dfs_find_par(int v) {
  for (int i = 1; i < LG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
  for (auto u : gr[v])
    if (u != par[v][0]) par[u][0] = v, h[u] = h[v] + 1, dfs_find_par(u);
}
void dfs_find_ghotr(int v, int p) {
  for (auto u : gr[v])
    if (u != p) hv[u] = hv[v] + 1, dfs_find_ghotr(u, v);
}
int k_par(int v, int k) {
  for (int i = LG - 1; i >= 0; i--)
    if (k & (1 << i)) v = par[v][i];
  return v;
}
int LCA(int u, int v) {
  if (h[v] > h[u]) swap(u, v);
  u = k_par(u, h[u] - h[v]);
  if (u == v) return v;
  for (int i = LG - 1; i >= 0; i--)
    if (par[v][i] != par[u][i]) u = par[u][i], v = par[v][i];
  return par[v][0];
}
int dis(int u, int v) { return h[v] + h[u] - 2 * h[LCA(u, v)]; }
void vis_ghotr(int u, int v) {
  int l = LCA(u, v);
  vis[l] = true;
  while (u != l) vis[u] = true, u = par[u][0];
  while (v != l) vis[v] = true, v = par[v][0];
}
void get_ord(int v, int p) {
  for (auto u : gr[v])
    if (u != p && !vis[u]) get_ord(u, v);
  if (vis[v]) return;
  int mx = U;
  if (dis(V, v) > dis(U, v)) mx = V;
  sum += dis(v, mx);
  ans.push_back({{mx, v}, v});
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  if (n == 2) return cout << 1 << endl << "1 2 1" << endl, 0;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    gr[u].push_back(v), gr[v].push_back(u);
  }
  int root = 1;
  if (gr[1].size() == 1)
    for (int i = 1; i <= n; i++)
      if (gr[i].size() != 1) root = i;
  dfs_find_par(root);
  V = 1;
  for (int i = 1; i <= n; i++)
    if (h[i] > h[V]) V = i;
  dfs_find_ghotr(V, -1);
  U = V;
  for (int i = 1; i <= n; i++)
    if (hv[i] > hv[U]) U = i;
  vis_ghotr(U, V);
  for (int i = 1; i <= n; i++)
    if (vis[i]) get_ord(i, -1);
  int l = LCA(U, V);
  while (U != l) {
    if (U == 0) break;
    sum += dis(U, V);
    ans.push_back({{U, V}, U});
    U = par[U][0];
  }
  while (V != l) {
    if (V == 0) break;
    sum += dis(V, l);
    ans.push_back({{V, l}, V});
    V = par[V][0];
  }
  cout << sum << '\n';
  for (int i = 0; i < ans.size(); i++)
    cout << ans[i].first.first << " " << ans[i].first.second << " "
         << ans[i].second << '\n';
  return 0;
}