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;
int n;
vector<int> gr[201010];
vector<int> trace;
vector<int> dis;
int bfs(int u) {
  trace.assign(n + 1, -1);
  dis.assign(n + 1, -1);
  trace[u] = u;
  dis[u] = 0;
  queue<int> qu;
  for (qu.push(u); qu.size(); qu.pop()) {
    u = qu.front();
    for (auto v : gr[u]) {
      if (trace[v] != -1) continue;
      trace[v] = u;
      dis[v] = dis[u] + 1;
      qu.push(v);
    }
  }
  return u;
}
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = -1; ++i < n - 1;) {
    int u, v;
    cin >> u >> v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  int diameter_end1 = bfs(1);
  int diameter_end2 = bfs(diameter_end1);
  vector<int> dis1 = move(dis);
  bfs(diameter_end2);
  vector<int> dis2 = move(dis);
  vector<pair<int, int>> ans;
  vector<bool> vis(n + 1);
  queue<int> qu;
  long long total_cost = 0;
  for (int u = diameter_end1; u != diameter_end2; u = trace[u]) {
    ans.push_back({trace[u], diameter_end1});
    total_cost += dis1[trace[u]];
    vis[u] = true;
    qu.push(u);
  }
  vis[diameter_end2] = true;
  for (; qu.size(); qu.pop()) {
    int u = qu.front();
    for (auto v : gr[u]) {
      if (vis[v]) continue;
      vis[v] = true;
      ans.emplace_back(v, dis2[v] < dis1[v] ? diameter_end1 : diameter_end2);
      total_cost += max(dis2[v], dis1[v]);
      qu.push(v);
    }
  }
  cout << total_cost << '\n';
  for (int i = ((int)ans.size()); i--;) {
    cout << ans[i].first << ' ' << ans[i].second << ' ' << ans[i].first << '\n';
  }
  return 0;
}