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 + 5;
vector<int> adj[N], X[N], Y[N];
int n, x, y, h[N], dp[N][2], id[N];
int dfs(int u, int par = -1) {
  int ver = u;
  h[u] = ~par ? h[par] + 1 : 0;
  for (auto v : adj[u])
    if (v ^ par) {
      int x = dfs(v, u);
      if (h[x] > h[ver]) ver = x;
    }
  return ver;
}
void dfs_dp(int u, int id, int par = -1) {
  for (auto v : adj[u])
    if (v ^ par) {
      dp[v][id] = dp[u][id] + 1;
      dfs_dp(v, id, u);
    }
}
void print(int u, int v) { cout << ++u << ' ' << ++v << ' ' << v << endl; }
void read_input() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[--u].push_back(--v);
    adj[v].push_back(u);
  }
}
void solve() {
  dfs_dp(x = dfs(0), 0);
  dfs_dp(y = dfs(x), 1);
  for (int u = 0; u < n; u++)
    if (dp[u][0] + dp[u][1] > dp[x][1])
      if (dp[u][0] > dp[u][1])
        X[dp[u][0]].push_back(u);
      else
        Y[dp[u][1]].push_back(u);
    else
      id[dp[u][0]] = u;
}
void write_output() {
  long long total = dp[x][1] * (dp[x][1] + 1LL) >> 1;
  for (int i = n; i; i--) total += 1LL * i * (X[i].size() + Y[i].size());
  cout << total << endl;
  for (int i = n; i; i--) {
    for (auto u : X[i]) print(x, u);
    for (auto u : Y[i]) print(y, u);
  }
  for (int i = dp[y][0]; i; i--) print(x, id[i]);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  read_input(), solve(), write_output();
  return 0;
}