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 = 1e9 + 7;
const long long linf = 1ll * inf * inf;
const int N = 200000 + 7;
const int M = 22;
const int multipleTest = 0;
int n;
vector<int> adj[N];
int d[N][2];
int pa[N];
int cnt[N];
bool checked = false;
void dfs(int u, int r, int type) {
  d[u][type] = (r == -1) ? 0 : (d[r][type] + 1);
  pa[u] = r;
  if (r != -1 && type == 1 && !checked) {
    cnt[r]++;
  }
  for (int v : adj[u]) {
    if (v != r) {
      dfs(v, u, type);
    }
  }
}
bool onStraigtLine[N];
void setLine(int s) {
  while (s != -1) {
    onStraigtLine[s] = true;
    s = pa[s];
  }
}
int stk[N], top;
long long ans;
vector<pair<pair<int, int>, int>> all;
void calc(int s, int t) {
  ans = 0;
  top = 0;
  for (int i = 1; i <= n; ++i)
    if (!onStraigtLine[i] && !cnt[i]) {
      stk[top++] = i;
    }
  for (int i = 0; i < top; ++i) {
    int u = stk[i];
    int root = d[u][0] >= d[u][1] ? s : t;
    ans += max(d[u][0], d[u][1]);
    all.push_back(make_pair(make_pair(u, root), u));
    if (pa[u] != -1 && !onStraigtLine[pa[u]]) {
      cnt[pa[u]]--;
      if (!cnt[pa[u]]) {
        stk[top++] = pa[u];
      }
    }
  }
  int dist = d[t][0];
  while (t != s) {
    ans += dist--;
    all.push_back(make_pair(make_pair(s, t), t));
    t = pa[t];
  }
}
void solve() {
  cin >> n;
  for (int i = (1), _b = (n); i < _b; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int curRoot = 1;
  dfs(curRoot, -1, 0);
  for (int i = 2; i <= n; ++i)
    if (d[i][0] > d[curRoot][0]) curRoot = i;
  dfs(curRoot, -1, 1);
  int nxtRoot = 1;
  for (int i = 2; i <= n; ++i)
    if (d[i][1] > d[nxtRoot][1]) nxtRoot = i;
  checked = true;
  dfs(nxtRoot, -1, 1);
  dfs(curRoot, -1, 0);
  setLine(nxtRoot);
  calc(curRoot, nxtRoot);
  cout << ans << '\n';
  for (auto x : all) {
    printf("%d %d %d\n", x.first.first, x.first.second, x.second);
  }
}
int main() {
  int Test = 1;
  if (multipleTest) cin >> Test;
  for (int i = 0; i < Test; ++i) {
    solve();
  }
}