#include <bits/stdc++.h>
using namespace std;
const int block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T &a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T>
inline void in(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A &x, B &y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
template <class T>
void upd(T &a, T b) {
  a = max(a, b);
}
namespace HLD {
struct edge {
  int to;
  edge(int x) : to(x) {}
};
const int root = 1;
const int maxn = 200010;
vector<edge> adj[maxn];
int dfnToID[maxn], dfn[maxn], head[maxn], fa[maxn], dep[maxn], size[maxn],
    heavy[maxn], r[maxn], cnt = 1;
void firstDfs(int cur, int _fa) {
  dep[cur] = dep[_fa] + 1;
  size[cur] = 1;
  fa[cur] = _fa;
  for (auto e : adj[cur]) {
    if (e.to != _fa) {
      firstDfs(e.to, cur);
      size[cur] += size[e.to];
    }
  }
  int heavyChild = 0;
  for (auto e : adj[cur]) {
    if (e.to != _fa) {
      if (size[e.to] > size[heavyChild]) {
        heavyChild = e.to;
      }
    }
  }
  heavy[cur] = heavyChild;
}
void secondDfs(int cur, int _fa) {
  if (cur != heavy[_fa]) {
    head[cur] = cur;
  } else {
    head[cur] = head[_fa];
  }
  dfn[cur] = cnt++;
  r[cur] = dfn[cur];
  dfnToID[dfn[cur]] = cur;
  if (!heavy[cur]) return;
  secondDfs(heavy[cur], cur);
  r[cur] = r[heavy[cur]];
  for (auto e : adj[cur]) {
    if (e.to == _fa || e.to == heavy[cur]) continue;
    secondDfs(e.to, cur);
    r[cur] = r[e.to];
  }
}
void init() {
  firstDfs(root, 0);
  secondDfs(root, 0);
}
int kthFather(int k, int cur) {
  while (k) {
    if (head[cur] == cur) {
      k--;
      cur = fa[head[cur]];
    } else {
      if (dep[cur] - dep[head[cur]] <= k) {
        k -= dep[cur] - dep[head[cur]];
        cur = head[cur];
      } else {
        return dfnToID[dfn[cur] - k];
      }
    }
  }
  return cur;
}
int LCA(int u, int v) {
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) swap(u, v);
    v = fa[head[v]];
  }
  if (dep[u] < dep[v]) return u;
  return v;
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }
}  // namespace HLD
vector<int> adj[200010];
int n;
const int maxn = 200010;
int len[maxn];
void dfs(int cur, int fa) {
  for (auto i : adj[cur]) {
    if (i != fa) {
      len[i] = len[cur] + 1;
      dfs(i, cur);
    }
  }
}
int getFarthest(int x) {
  memset(len, -1, sizeof(len));
  len[x] = 0;
  dfs(x, 0);
  pair<int, int> ans = make_pair(len[1], 1);
  for (long long i = 1; i < n + 1; i++)
    ans = max(ans, make_pair(len[i], (int)i));
  return ans.second;
}
pair<int, int> getDiam() {
  int a = getFarthest(1);
  int b = getFarthest(a);
  return make_pair(a, b);
}
int deg[maxn];
vector<pair<int, int> > op;
long long ans = 0;
bool rem[maxn];
void bfs(pair<int, int> diam) {
  long long ans = 0;
  for (long long i = 1; i < n + 1; i++) {
    for (auto j : adj[i]) deg[j]++;
  }
  queue<int> q;
  for (long long i = 1; i < n + 1; i++) {
    if (deg[i] == 1 && i != diam.first && i != diam.second) {
      q.push(i);
      rem[i] = 1;
    }
  }
  while (((int)q.size())) {
    int f = q.front();
    q.pop();
    int dis[] = {HLD::dis(f, diam.first), HLD::dis(f, diam.second)};
    if (dis[0] > dis[1]) {
      op.push_back(make_pair(f, diam.first));
      ans += dis[0];
    } else {
      op.push_back(make_pair(f, diam.second));
      ans += dis[1];
    }
    for (auto to : adj[f]) {
      deg[to]--;
      if (rem[to]) continue;
      if (to != diam.first && to != diam.second && deg[to] == 1) {
        q.push(to);
      }
    }
  }
  q.push(diam.first);
  while (((int)q.size())) {
    int f = q.front();
    q.pop();
    int dis[] = {HLD::dis(f, diam.first), HLD::dis(f, diam.second)};
    op.push_back(make_pair(f, diam.second));
    ans += dis[1];
    for (auto to : adj[f]) {
      deg[to]--;
      if (rem[to]) continue;
      if (to != diam.first && to != diam.second && deg[to] == 1) {
        q.push(to);
      }
    }
  }
  cout << ans << endl;
  for (auto i : op) {
    printf("%d %d %d\n", i.first, i.second, i.first);
  }
}
int main() {
  in(n);
  for (long long i = 1; i < n; i++) {
    int u, v;
    in(u, v);
    HLD::adj[u].push_back(HLD::edge(v));
    HLD::adj[v].push_back(HLD::edge(u));
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  HLD::init();
  auto diam = getDiam();
  cerr << "diam.fi"
       << " = " << (diam.first) << endl;
  ;
  cerr << "diam.se"
       << " = " << (diam.second) << endl;
  ;
  bfs(diam);
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
using namespace std;
const int block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T &a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T>
inline void in(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A &x, B &y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
template <class T>
void upd(T &a, T b) {
  a = max(a, b);
}
namespace HLD {
struct edge {
  int to;
  edge(int x) : to(x) {}
};
const int root = 1;
const int maxn = 200010;
vector<edge> adj[maxn];
int dfnToID[maxn], dfn[maxn], head[maxn], fa[maxn], dep[maxn], size[maxn],
    heavy[maxn], r[maxn], cnt = 1;
void firstDfs(int cur, int _fa) {
  dep[cur] = dep[_fa] + 1;
  size[cur] = 1;
  fa[cur] = _fa;
  for (auto e : adj[cur]) {
    if (e.to != _fa) {
      firstDfs(e.to, cur);
      size[cur] += size[e.to];
    }
  }
  int heavyChild = 0;
  for (auto e : adj[cur]) {
    if (e.to != _fa) {
      if (size[e.to] > size[heavyChild]) {
        heavyChild = e.to;
      }
    }
  }
  heavy[cur] = heavyChild;
}
void secondDfs(int cur, int _fa) {
  if (cur != heavy[_fa]) {
    head[cur] = cur;
  } else {
    head[cur] = head[_fa];
  }
  dfn[cur] = cnt++;
  r[cur] = dfn[cur];
  dfnToID[dfn[cur]] = cur;
  if (!heavy[cur]) return;
  secondDfs(heavy[cur], cur);
  r[cur] = r[heavy[cur]];
  for (auto e : adj[cur]) {
    if (e.to == _fa || e.to == heavy[cur]) continue;
    secondDfs(e.to, cur);
    r[cur] = r[e.to];
  }
}
void init() {
  firstDfs(root, 0);
  secondDfs(root, 0);
}
int kthFather(int k, int cur) {
  while (k) {
    if (head[cur] == cur) {
      k--;
      cur = fa[head[cur]];
    } else {
      if (dep[cur] - dep[head[cur]] <= k) {
        k -= dep[cur] - dep[head[cur]];
        cur = head[cur];
      } else {
        return dfnToID[dfn[cur] - k];
      }
    }
  }
  return cur;
}
int LCA(int u, int v) {
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) swap(u, v);
    v = fa[head[v]];
  }
  if (dep[u] < dep[v]) return u;
  return v;
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }
}  // namespace HLD
vector<int> adj[200010];
int n;
const int maxn = 200010;
int len[maxn];
void dfs(int cur, int fa) {
  for (auto i : adj[cur]) {
    if (i != fa) {
      len[i] = len[cur] + 1;
      dfs(i, cur);
    }
  }
}
int getFarthest(int x) {
  memset(len, -1, sizeof(len));
  len[x] = 0;
  dfs(x, 0);
  pair<int, int> ans = make_pair(len[1], 1);
  for (long long i = 1; i < n + 1; i++)
    ans = max(ans, make_pair(len[i], (int)i));
  return ans.second;
}
pair<int, int> getDiam() {
  int a = getFarthest(1);
  int b = getFarthest(a);
  return make_pair(a, b);
}
int deg[maxn];
vector<pair<int, int> > op;
long long ans = 0;
bool rem[maxn];
void bfs(pair<int, int> diam) {
  long long ans = 0;
  for (long long i = 1; i < n + 1; i++) {
    for (auto j : adj[i]) deg[j]++;
  }
  queue<int> q;
  for (long long i = 1; i < n + 1; i++) {
    if (deg[i] == 1 && i != diam.first && i != diam.second) {
      q.push(i);
      rem[i] = 1;
    }
  }
  while (((int)q.size())) {
    int f = q.front();
    q.pop();
    int dis[] = {HLD::dis(f, diam.first), HLD::dis(f, diam.second)};
    if (dis[0] > dis[1]) {
      op.push_back(make_pair(f, diam.first));
      ans += dis[0];
    } else {
      op.push_back(make_pair(f, diam.second));
      ans += dis[1];
    }
    for (auto to : adj[f]) {
      deg[to]--;
      if (rem[to]) continue;
      if (to != diam.first && to != diam.second && deg[to] == 1) {
        q.push(to);
      }
    }
  }
  q.push(diam.first);
  while (((int)q.size())) {
    int f = q.front();
    q.pop();
    int dis[] = {HLD::dis(f, diam.first), HLD::dis(f, diam.second)};
    op.push_back(make_pair(f, diam.second));
    ans += dis[1];
    for (auto to : adj[f]) {
      deg[to]--;
      if (rem[to]) continue;
      if (to != diam.first && to != diam.second && deg[to] == 1) {
        q.push(to);
      }
    }
  }
  cout << ans << endl;
  for (auto i : op) {
    printf("%d %d %d\n", i.first, i.second, i.first);
  }
}
int main() {
  in(n);
  for (long long i = 1; i < n; i++) {
    int u, v;
    in(u, v);
    HLD::adj[u].push_back(HLD::edge(v));
    HLD::adj[v].push_back(HLD::edge(u));
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  HLD::init();
  auto diam = getDiam();
  cerr << "diam.fi"
       << " = " << (diam.first) << endl;
  ;
  cerr << "diam.se"
       << " = " << (diam.second) << endl;
  ;
  bfs(diam);
  return 0;
}

```