#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
vector<int> g[200011];
int parent[200011][19];
int depth[200011];
int height[200011];
int far[200011];
void dfs(int v, int pre) {
  depth[v] = depth[pre] + 1;
  parent[v][0] = pre;
  int i;
  for (i = 1; i <= 18; ++i) parent[v][i] = parent[parent[v][i - 1]][i - 1];
  for (auto nv : g[v]) {
    if (nv != pre) {
      dfs(nv, v);
    }
  }
}
int dfs2(int v, int pre) {
  for (auto nv : g[v]) {
    if (nv != pre) {
      int p = dfs2(nv, v);
      height[v] = max(1 + p, height[v]);
    }
  }
  return height[v];
}
void dfs3(int v, int pre) {
  multiset<int> st;
  for (auto nv : g[v]) {
    if (nv != pre) {
      st.insert(height[nv]);
    }
  }
  for (auto nv : g[v]) {
    if (nv != pre) {
      far[nv] = far[v] + 1;
      st.erase(st.find(height[nv]));
      if (!st.empty()) {
        far[nv] = max(far[nv], 2 + *st.rbegin());
      }
      st.insert(height[nv]);
    }
  }
  for (auto nv : g[v]) {
    if (nv != pre) {
      dfs3(nv, v);
    }
  }
}
int LCA(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  int i;
  for (i = 18; i >= 0; --i) {
    if (depth[u] >= (1 << i) + depth[v]) {
      u = parent[u][i];
    }
  }
  if (u == v) return u;
  for (i = 18; i >= 0; --i) {
    if (parent[u][i] != parent[v][i]) {
      u = parent[u][i];
      v = parent[v][i];
    }
  }
  return parent[u][0];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[LCA(u, v)]; }
vector<pair<pair<int, int>, int>> ans;
bool nodim[200011];
int deg[200011];
bool visited[200011];
int main() {
  int i, n;
  scanf("%d", &n);
  for (i = 0; i < n - 1; ++i) {
    int v1, v2;
    scanf("%d%d", &v1, &v2);
    g[v1].push_back(v2);
    g[v2].push_back(v1);
    deg[v1]++, deg[v2]++;
  }
  if (n == 2) {
    printf("1\n");
    printf("1 2 1\n");
    return 0;
  }
  dfs(1, 0);
  dfs2(1, 0);
  dfs3(1, 0);
  int ht = 0, rt = 1, rt2 = 1;
  for (i = 1; i <= n; ++i) {
    far[i] = max(far[i], height[i]);
    if (far[i] > ht) {
      ht = far[i], rt = i;
    }
  }
  for (i = 1; i <= n; ++i) {
    if (dist(i, rt) == far[rt]) {
      rt2 = i;
      break;
    }
  }
  long long cost = 0;
  queue<int> q;
  for (i = 1; i <= n; ++i) {
    int d1 = dist(i, rt), d2 = dist(i, rt2);
    if (d1 + d2 != far[rt]) {
      cost += max(d1, d2);
      nodim[i] = true;
      if (deg[i] == 1) {
        q.push(i);
      }
    }
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (visited[v]) continue;
    visited[v] = true;
    int d1 = dist(v, rt), d2 = dist(v, rt2);
    if (d1 >= d2) {
      ans.push_back(make_pair(make_pair(v, rt), v));
    } else {
      ans.push_back(make_pair(make_pair(v, rt2), v));
    }
    for (auto nv : g[v]) {
      if (nodim[nv] && !visited[nv]) {
        --deg[nv];
        if (deg[nv] == 1) {
          q.push(nv);
        }
      }
    }
  }
  int d = far[rt];
  while (rt2 != rt) {
    cost += d--;
    ans.push_back(make_pair(make_pair(rt, rt2), rt2));
    for (auto v : g[rt2]) {
      if (dist(v, rt) == d) {
        rt2 = v;
        break;
      }
    }
  }
  printf("%I64d\n", cost);
  for (auto p : ans) {
    printf("%d %d %d\n", p.first.first, p.first.second, p.second);
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
vector<int> g[200011];
int parent[200011][19];
int depth[200011];
int height[200011];
int far[200011];
void dfs(int v, int pre) {
  depth[v] = depth[pre] + 1;
  parent[v][0] = pre;
  int i;
  for (i = 1; i <= 18; ++i) parent[v][i] = parent[parent[v][i - 1]][i - 1];
  for (auto nv : g[v]) {
    if (nv != pre) {
      dfs(nv, v);
    }
  }
}
int dfs2(int v, int pre) {
  for (auto nv : g[v]) {
    if (nv != pre) {
      int p = dfs2(nv, v);
      height[v] = max(1 + p, height[v]);
    }
  }
  return height[v];
}
void dfs3(int v, int pre) {
  multiset<int> st;
  for (auto nv : g[v]) {
    if (nv != pre) {
      st.insert(height[nv]);
    }
  }
  for (auto nv : g[v]) {
    if (nv != pre) {
      far[nv] = far[v] + 1;
      st.erase(st.find(height[nv]));
      if (!st.empty()) {
        far[nv] = max(far[nv], 2 + *st.rbegin());
      }
      st.insert(height[nv]);
    }
  }
  for (auto nv : g[v]) {
    if (nv != pre) {
      dfs3(nv, v);
    }
  }
}
int LCA(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  int i;
  for (i = 18; i >= 0; --i) {
    if (depth[u] >= (1 << i) + depth[v]) {
      u = parent[u][i];
    }
  }
  if (u == v) return u;
  for (i = 18; i >= 0; --i) {
    if (parent[u][i] != parent[v][i]) {
      u = parent[u][i];
      v = parent[v][i];
    }
  }
  return parent[u][0];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[LCA(u, v)]; }
vector<pair<pair<int, int>, int>> ans;
bool nodim[200011];
int deg[200011];
bool visited[200011];
int main() {
  int i, n;
  scanf("%d", &n);
  for (i = 0; i < n - 1; ++i) {
    int v1, v2;
    scanf("%d%d", &v1, &v2);
    g[v1].push_back(v2);
    g[v2].push_back(v1);
    deg[v1]++, deg[v2]++;
  }
  if (n == 2) {
    printf("1\n");
    printf("1 2 1\n");
    return 0;
  }
  dfs(1, 0);
  dfs2(1, 0);
  dfs3(1, 0);
  int ht = 0, rt = 1, rt2 = 1;
  for (i = 1; i <= n; ++i) {
    far[i] = max(far[i], height[i]);
    if (far[i] > ht) {
      ht = far[i], rt = i;
    }
  }
  for (i = 1; i <= n; ++i) {
    if (dist(i, rt) == far[rt]) {
      rt2 = i;
      break;
    }
  }
  long long cost = 0;
  queue<int> q;
  for (i = 1; i <= n; ++i) {
    int d1 = dist(i, rt), d2 = dist(i, rt2);
    if (d1 + d2 != far[rt]) {
      cost += max(d1, d2);
      nodim[i] = true;
      if (deg[i] == 1) {
        q.push(i);
      }
    }
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (visited[v]) continue;
    visited[v] = true;
    int d1 = dist(v, rt), d2 = dist(v, rt2);
    if (d1 >= d2) {
      ans.push_back(make_pair(make_pair(v, rt), v));
    } else {
      ans.push_back(make_pair(make_pair(v, rt2), v));
    }
    for (auto nv : g[v]) {
      if (nodim[nv] && !visited[nv]) {
        --deg[nv];
        if (deg[nv] == 1) {
          q.push(nv);
        }
      }
    }
  }
  int d = far[rt];
  while (rt2 != rt) {
    cost += d--;
    ans.push_back(make_pair(make_pair(rt, rt2), rt2));
    for (auto v : g[rt2]) {
      if (dist(v, rt) == d) {
        rt2 = v;
        break;
      }
    }
  }
  printf("%I64d\n", cost);
  for (auto p : ans) {
    printf("%d %d %d\n", p.first.first, p.first.second, p.second);
  }
  return 0;
}

```