#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
struct HLDecomposition {
  vector<set<int>> g;
  vector<int> vid, head, heavy, parent, depth, inv;
  HLDecomposition() {}
  HLDecomposition(int n) { init(n); }
  void init(int n) {
    g.resize(n);
    vid.resize(n, -1);
    head.resize(n);
    heavy.resize(n, -1);
    parent.resize(n);
    depth.resize(n);
    inv.resize(n);
  }
  void add(int u, int v) {
    g[u].insert(v);
    g[v].insert(u);
  }
  void build() {
    dfs(0, -1);
    bfs();
  }
  int dfs(int curr, int prev) {
    parent[curr] = prev;
    int sub = 1, max_sub = 0;
    for (int next : g[curr])
      if (next != prev) {
        depth[next] = depth[curr] + 1;
        int sub_next = dfs(next, curr);
        sub += sub_next;
        if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
      }
    return sub;
  }
  void bfs() {
    int k = 0;
    queue<int> q({0});
    while (!q.empty()) {
      int h = q.front();
      q.pop();
      for (int i = h; i != -1; i = heavy[i]) {
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for (int j : g[i])
          if (j != parent[i] && j != heavy[i]) q.push(j);
      }
    }
  }
  void foreach (int u, int v, function<void(int, int)> f) {
    if (vid[u] > vid[v]) swap(u, v);
    f(max(vid[head[v]], vid[u]), vid[v]);
    if (head[u] != head[v]) foreach (u, parent[head[v]], f)
        ;
  }
  int ancestor(int from, int times) {
    while (true) {
      if (depth[head[from]] > depth[from] - times) {
        times -= depth[from] - depth[head[from]] + 1;
        if (head[from] == 0) return -1;
        from = parent[head[from]];
      } else
        return inv[vid[from] - times];
    }
  }
  int lca(int u, int v) {
    if (vid[u] > vid[v]) swap(u, v);
    if (head[u] == head[v]) return u;
    return lca(u, parent[head[v]]);
  }
  int distance(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  }
  int child(int parent, int child, int times) {
    assert(depth[parent] < depth[child]);
    int d = distance(parent, child);
    assert(times - 1 <= d);
    return ancestor(child, d - times);
  }
  int go(int from, int to, int times) {
    int d = distance(from, to);
    assert(0 <= times and times <= d);
    int lc = lca(from, to);
    if (lc == to) return ancestor(from, times);
    if (lc == from) return child(from, to, times);
    int dd = distance(from, lc);
    if (dd <= times) return go(lc, to, times - dd);
    return ancestor(from, times);
  }
};
struct TreeDiameter {
  int N;
  vector<set<int>> E;
  TreeDiameter() {}
  TreeDiameter(int _N) { init(_N); }
  void init(int _N) {
    N = _N;
    E.resize(N);
  }
  void add_edge(int a, int b) {
    E[a].insert(b);
    E[b].insert(a);
  }
  void build() {
    vector<int> dv(N), dw(N);
    for (int i = 0; i < N; i++) dv[i] = 0;
    dfs(0, -1, dv);
    v = 0;
    for (int i = 0; i < N; i++)
      if (dv[i] > dv[v]) v = i;
    for (int i = 0; i < N; i++) dv[i] = 0;
    dfs(v, -1, dv);
    w = 0;
    for (int i = 0; i < N; i++)
      if (dv[i] > dv[w]) w = i;
    for (int i = 0; i < N; i++) dw[i] = 0;
    dfs(w, -1, dw);
    dia = dv[w];
    if (dia % 2 == 0) {
      int R = dia / 2;
      for (int i = 0; i < N; i++)
        if (dv[i] == R && dw[i] == R) cent_even = i;
      vector<int> dc(N, 0);
      dfs(cent_even, -1, dc);
      for (int i = 0; i < N; i++)
        if (dc[i] == R) leaf_even.push_back(i);
    } else {
      int R = dia / 2;
      int c1 = 0, c2 = 0;
      for (int i = 0; i < N; i++)
        if (dv[i] == R && dw[i] == R + 1) c1 = i;
      for (int i = 0; i < N; i++)
        if (dv[i] == R + 1 && dw[i] == R) c2 = i;
      cent_odd = {c1, c2};
      vector<int> dc1(N, 0);
      dfs(c1, -1, dc1);
      vector<int> dc2(N, 0);
      dfs(c2, -1, dc2);
      for (int i = 0; i < N; i++)
        if (dc1[i] == R && dc2[i] == R + 1) leaf_odd.first.push_back(i);
      for (int i = 0; i < N; i++)
        if (dc1[i] == R + 1 && dc2[i] == R) leaf_odd.second.push_back(i);
    }
    vector<int> cn(N);
    dfs2(0, -1, cn);
    int mi = N + 1;
    for (int i = 0; i < N; i++) {
      int d = N - cn[i];
      for (auto& to : E[i])
        if (cn[to] < cn[i]) d = max(d, cn[to]);
      if (d < mi) {
        mi = d;
        centroid.clear();
        centroid.push_back(i);
      } else if (d == mi)
        centroid.push_back(i);
    }
  }
  void dfs(int cu, int pa, vector<int>& D) {
    for (auto& to : E[cu])
      if (to != pa) {
        D[to] = D[cu] + 1;
        dfs(to, cu, D);
      }
  }
  void dfs2(int cu, int pa, vector<int>& cn) {
    cn[cu] = 1;
    for (auto& to : E[cu])
      if (to != pa) {
        dfs2(to, cu, cn);
        cn[cu] += cn[to];
      }
  }
  int v, w, dia;
  int cent_even;
  vector<int> leaf_even;
  pair<int, int> cent_odd;
  pair<vector<int>, vector<int>> leaf_odd;
  vector<int> centroid;
};
int N;
vector<int> E[201010];
HLDecomposition hld;
TreeDiameter td;
long long ans1 = 0;
vector<tuple<int, int, int>> ans2;
int clr[201010];
int ai, bi;
void dfs(int cu, int pa, int col) {
  clr[cu] = col;
  for (auto& to : E[cu])
    if (to != pa) dfs(to, cu, col);
}
int dep[201010];
void dfs2(int cu, int pa) {
  for (auto& to : E[cu])
    if (to != pa) {
      dep[to] = dep[cu] + 1;
      dfs2(to, cu);
    }
}
void solve1() {
  int c = td.cent_even;
  int co = 0;
  dep[c] = 0;
  for (auto& to : E[c]) {
    dfs(to, c, co);
    co++;
    dep[to] = 1;
    dfs2(to, c);
  }
  map<int, int> leader;
  for (auto& lef : td.leaf_even) leader[clr[lef]] = lef;
  auto ite = leader.begin();
  ai = ite->second;
  ite++;
  bi = ite->second;
}
void solve2() {
  ai = td.leaf_odd.first[0];
  bi = td.leaf_odd.second[0];
  dep[ai] = dep[bi] = 0;
  dfs2(ai, bi);
  dfs2(bi, ai);
}
void _main() {
  cin >> N;
  hld.init(N);
  td.init(N);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    hld.add(a, b);
    td.add_edge(a, b);
    E[a].push_back(b);
    E[b].push_back(a);
  }
  hld.build();
  td.build();
  if (td.dia % 2 == 0)
    solve1();
  else
    solve2();
  vector<pair<int, int>> v;
  for (int i = 0; i < N; i++) v.push_back({dep[i], i});
  sort(v.begin(), v.end(), greater<pair<int, int>>());
  for (int _ = 0; _ < N; _++) {
    int i = v[_].second;
    if (ai != i and bi != i) {
      int d = hld.distance(ai, bi);
      int d1 = hld.distance(ai, i);
      int d2 = hld.distance(bi, i);
      if (d1 + d2 == d) continue;
      if (d1 < d2) {
        ans1 += d2;
        ans2.push_back(make_tuple(bi, i, i));
      } else {
        ans1 += d1;
        ans2.push_back(make_tuple(ai, i, i));
      }
    }
  }
  while (ai != bi) {
    ans1 += hld.distance(ai, bi);
    ans2.push_back(make_tuple(ai, bi, ai));
    ai = hld.go(ai, bi, 1);
  }
  printf("%lld\n", ans1);
  for (auto& t : ans2) {
    int a, b, c;
    tie(a, b, c) = t;
    printf("%d %d %d\n", a + 1, b + 1, c + 1);
  }
}

### Prompt

Your challenge is to write 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("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
struct HLDecomposition {
  vector<set<int>> g;
  vector<int> vid, head, heavy, parent, depth, inv;
  HLDecomposition() {}
  HLDecomposition(int n) { init(n); }
  void init(int n) {
    g.resize(n);
    vid.resize(n, -1);
    head.resize(n);
    heavy.resize(n, -1);
    parent.resize(n);
    depth.resize(n);
    inv.resize(n);
  }
  void add(int u, int v) {
    g[u].insert(v);
    g[v].insert(u);
  }
  void build() {
    dfs(0, -1);
    bfs();
  }
  int dfs(int curr, int prev) {
    parent[curr] = prev;
    int sub = 1, max_sub = 0;
    for (int next : g[curr])
      if (next != prev) {
        depth[next] = depth[curr] + 1;
        int sub_next = dfs(next, curr);
        sub += sub_next;
        if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
      }
    return sub;
  }
  void bfs() {
    int k = 0;
    queue<int> q({0});
    while (!q.empty()) {
      int h = q.front();
      q.pop();
      for (int i = h; i != -1; i = heavy[i]) {
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for (int j : g[i])
          if (j != parent[i] && j != heavy[i]) q.push(j);
      }
    }
  }
  void foreach (int u, int v, function<void(int, int)> f) {
    if (vid[u] > vid[v]) swap(u, v);
    f(max(vid[head[v]], vid[u]), vid[v]);
    if (head[u] != head[v]) foreach (u, parent[head[v]], f)
        ;
  }
  int ancestor(int from, int times) {
    while (true) {
      if (depth[head[from]] > depth[from] - times) {
        times -= depth[from] - depth[head[from]] + 1;
        if (head[from] == 0) return -1;
        from = parent[head[from]];
      } else
        return inv[vid[from] - times];
    }
  }
  int lca(int u, int v) {
    if (vid[u] > vid[v]) swap(u, v);
    if (head[u] == head[v]) return u;
    return lca(u, parent[head[v]]);
  }
  int distance(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  }
  int child(int parent, int child, int times) {
    assert(depth[parent] < depth[child]);
    int d = distance(parent, child);
    assert(times - 1 <= d);
    return ancestor(child, d - times);
  }
  int go(int from, int to, int times) {
    int d = distance(from, to);
    assert(0 <= times and times <= d);
    int lc = lca(from, to);
    if (lc == to) return ancestor(from, times);
    if (lc == from) return child(from, to, times);
    int dd = distance(from, lc);
    if (dd <= times) return go(lc, to, times - dd);
    return ancestor(from, times);
  }
};
struct TreeDiameter {
  int N;
  vector<set<int>> E;
  TreeDiameter() {}
  TreeDiameter(int _N) { init(_N); }
  void init(int _N) {
    N = _N;
    E.resize(N);
  }
  void add_edge(int a, int b) {
    E[a].insert(b);
    E[b].insert(a);
  }
  void build() {
    vector<int> dv(N), dw(N);
    for (int i = 0; i < N; i++) dv[i] = 0;
    dfs(0, -1, dv);
    v = 0;
    for (int i = 0; i < N; i++)
      if (dv[i] > dv[v]) v = i;
    for (int i = 0; i < N; i++) dv[i] = 0;
    dfs(v, -1, dv);
    w = 0;
    for (int i = 0; i < N; i++)
      if (dv[i] > dv[w]) w = i;
    for (int i = 0; i < N; i++) dw[i] = 0;
    dfs(w, -1, dw);
    dia = dv[w];
    if (dia % 2 == 0) {
      int R = dia / 2;
      for (int i = 0; i < N; i++)
        if (dv[i] == R && dw[i] == R) cent_even = i;
      vector<int> dc(N, 0);
      dfs(cent_even, -1, dc);
      for (int i = 0; i < N; i++)
        if (dc[i] == R) leaf_even.push_back(i);
    } else {
      int R = dia / 2;
      int c1 = 0, c2 = 0;
      for (int i = 0; i < N; i++)
        if (dv[i] == R && dw[i] == R + 1) c1 = i;
      for (int i = 0; i < N; i++)
        if (dv[i] == R + 1 && dw[i] == R) c2 = i;
      cent_odd = {c1, c2};
      vector<int> dc1(N, 0);
      dfs(c1, -1, dc1);
      vector<int> dc2(N, 0);
      dfs(c2, -1, dc2);
      for (int i = 0; i < N; i++)
        if (dc1[i] == R && dc2[i] == R + 1) leaf_odd.first.push_back(i);
      for (int i = 0; i < N; i++)
        if (dc1[i] == R + 1 && dc2[i] == R) leaf_odd.second.push_back(i);
    }
    vector<int> cn(N);
    dfs2(0, -1, cn);
    int mi = N + 1;
    for (int i = 0; i < N; i++) {
      int d = N - cn[i];
      for (auto& to : E[i])
        if (cn[to] < cn[i]) d = max(d, cn[to]);
      if (d < mi) {
        mi = d;
        centroid.clear();
        centroid.push_back(i);
      } else if (d == mi)
        centroid.push_back(i);
    }
  }
  void dfs(int cu, int pa, vector<int>& D) {
    for (auto& to : E[cu])
      if (to != pa) {
        D[to] = D[cu] + 1;
        dfs(to, cu, D);
      }
  }
  void dfs2(int cu, int pa, vector<int>& cn) {
    cn[cu] = 1;
    for (auto& to : E[cu])
      if (to != pa) {
        dfs2(to, cu, cn);
        cn[cu] += cn[to];
      }
  }
  int v, w, dia;
  int cent_even;
  vector<int> leaf_even;
  pair<int, int> cent_odd;
  pair<vector<int>, vector<int>> leaf_odd;
  vector<int> centroid;
};
int N;
vector<int> E[201010];
HLDecomposition hld;
TreeDiameter td;
long long ans1 = 0;
vector<tuple<int, int, int>> ans2;
int clr[201010];
int ai, bi;
void dfs(int cu, int pa, int col) {
  clr[cu] = col;
  for (auto& to : E[cu])
    if (to != pa) dfs(to, cu, col);
}
int dep[201010];
void dfs2(int cu, int pa) {
  for (auto& to : E[cu])
    if (to != pa) {
      dep[to] = dep[cu] + 1;
      dfs2(to, cu);
    }
}
void solve1() {
  int c = td.cent_even;
  int co = 0;
  dep[c] = 0;
  for (auto& to : E[c]) {
    dfs(to, c, co);
    co++;
    dep[to] = 1;
    dfs2(to, c);
  }
  map<int, int> leader;
  for (auto& lef : td.leaf_even) leader[clr[lef]] = lef;
  auto ite = leader.begin();
  ai = ite->second;
  ite++;
  bi = ite->second;
}
void solve2() {
  ai = td.leaf_odd.first[0];
  bi = td.leaf_odd.second[0];
  dep[ai] = dep[bi] = 0;
  dfs2(ai, bi);
  dfs2(bi, ai);
}
void _main() {
  cin >> N;
  hld.init(N);
  td.init(N);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    hld.add(a, b);
    td.add_edge(a, b);
    E[a].push_back(b);
    E[b].push_back(a);
  }
  hld.build();
  td.build();
  if (td.dia % 2 == 0)
    solve1();
  else
    solve2();
  vector<pair<int, int>> v;
  for (int i = 0; i < N; i++) v.push_back({dep[i], i});
  sort(v.begin(), v.end(), greater<pair<int, int>>());
  for (int _ = 0; _ < N; _++) {
    int i = v[_].second;
    if (ai != i and bi != i) {
      int d = hld.distance(ai, bi);
      int d1 = hld.distance(ai, i);
      int d2 = hld.distance(bi, i);
      if (d1 + d2 == d) continue;
      if (d1 < d2) {
        ans1 += d2;
        ans2.push_back(make_tuple(bi, i, i));
      } else {
        ans1 += d1;
        ans2.push_back(make_tuple(ai, i, i));
      }
    }
  }
  while (ai != bi) {
    ans1 += hld.distance(ai, bi);
    ans2.push_back(make_tuple(ai, bi, ai));
    ai = hld.go(ai, bi, 1);
  }
  printf("%lld\n", ans1);
  for (auto& t : ans2) {
    int a, b, c;
    tie(a, b, c) = t;
    printf("%d %d %d\n", a + 1, b + 1, c + 1);
  }
}

```