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 long double EPS = 1e-10;
const long long MOD = 1e9 + 7;
const long double PI = 3.1415926535897932384626433832795028841;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
ostream& operator<<(std::ostream& stream, const long long* arr) {
  int i = 0;
  cout << "{";
  while (arr[i] != INT_MAX) {
    cout << arr[i];
    if (arr[i + 1] != INT_MAX) cout << ",";
    i++;
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream, const vector<int> vec) {
  cout << "{";
  for (int i = 0; i < vec.size(); i++) {
    cout << vec[i];
    if (i != vec.size() - 1) cout << ",";
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream,
                    const pair<long long, long long>& vec) {
  cout << "(" << vec.first << ',' << vec.second << ")";
  return stream;
}
template <class T>
struct segtree_t {
  vector<T> t, lazy, flag_equal;
  int st, sz;
  T (*addition_fun)(T, T);
  T invalid_value;
  segtree_t() {}
  segtree_t(int start, int finish, T* arr, T (*add_fun)(T, T), T invalid_val) {
    int size = (finish + 1) * 2;
    int tree_size = 2;
    while (tree_size < size) tree_size *= 2;
    t = vector<T>(tree_size);
    lazy = vector<T>(tree_size);
    flag_equal = vector<T>(tree_size);
    st = start;
    sz = finish;
    addition_fun = add_fun;
    invalid_value = invalid_val;
    build(1, start, finish, arr);
  }
  void build(int i, int l, int r, T* arr) {
    if (l > r) return;
    lazy[i] = 0;
    flag_equal[i] = 0;
    if (l == r) {
      t[i] = arr[l];
    } else {
      build(i * 2, l, (l + r) / 2, arr);
      build(i * 2 + 1, (l + r) / 2 + 1, r, arr);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  void inc_range(int l, int r, T value) {
    if (l > r) return;
    inc_range_rec(1, st, sz, l, r, value);
  }
  void set_values(int l, int r, T value) {
    set_values_rec(1, st, sz, l, r, value);
  }
  void inc_range_rec(int i, int l, int r, int tl, int tr, T value) {
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (r < tl or l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      if (l != r) {
        lazy[i * 2] += value;
        lazy[i * 2 + 1] += value;
      }
      t[i] += value;
    } else {
      inc_range_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      inc_range_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  T query_rec(int i, int l, int r, int tl, int tr) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl or l > tr) return invalid_value;
    if (l > r) return invalid_value;
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (l >= tl and r <= tr) {
      return t[i];
    } else {
      T m1 = query_rec(i * 2, l, (l + r) / 2, tl, tr);
      T m2 = query_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr);
      if (m1 == invalid_value && m2 == invalid_value) return invalid_value;
      if (m1 == invalid_value) return m2;
      if (m2 == invalid_value) return m1;
      return addition_fun(m1, m2);
    }
  }
  T query(int l, int r) { return query_rec(1, st, sz, l, r); }
  void set_values_rec(int i, int l, int r, int tl, int tr, T value) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl || l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      t[i] = value;
      flag_equal[i] = 1;
    } else {
      set_values_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      set_values_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  ~segtree_t() {}
};
template <class T>
struct fenwick_t {
  vector<T> FW;
  fenwick_t(int n) { FW = vector<T>(n + 1); }
  void inc(int i, T v) {
    while (i <= FW.size() - 1) {
      FW[i] += v;
      i += i & (-i);
    }
  }
  T get(int i) {
    T rta = 0;
    while (i > 0) {
      rta += FW[i];
      i -= i & (-i);
    }
    return rta;
  }
};
struct dsu_t {
  vector<int> p, sz, depth;
  dsu_t() {}
  dsu_t(int n) {
    p = vector<int>(n + 1);
    sz = vector<int>(n + 1);
    depth = vector<int>(n + 1);
    for (int i = 1; i <= n; i++) {
      p[i] = i;
      sz[i] = 1;
      depth[i] = 1;
    }
  }
  int get(int i) {
    int j = i;
    while (p[i] != i) i = p[i];
    while (p[j] != j) {
      int aux = p[j];
      p[j] = i;
      j = aux;
    }
    return i;
  }
  void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) {
      p[b] = a;
      sz[a] += sz[b];
    } else {
      p[a] = b;
      sz[b] += sz[a];
      if (depth[a] == depth[b]) depth[b]++;
    }
  }
  void show() {
    for (int i = 1; i <= p.size() - 1; i++) {
      cout << i << ": " << p[i] << ' ' << sz[i] << ' ' << depth[i] << " \n";
    }
  }
};
const int maxn = 2 * 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxk = 1e5 + 5;
const int maxq = 1e5 + 5;
long long n;
vector<long long> CONN[maxn];
long long CONNSZ[maxn];
queue<long long> leafs;
long long arr0[maxn], arr1[maxn], arr2[maxn], dead[maxn];
long long pa1[maxn], pa2[maxn], pa3[maxn];
long long leaf1, leaf2;
long long bfs1(long long* depth, long long u, long long* pa) {
  queue<long long> Q;
  Q.push(u);
  fill(depth + 1, depth + n + 1, -1);
  depth[u] = 0;
  while (!Q.empty()) {
    long long act = Q.front();
    Q.pop();
    for (long long i = 0; i < CONN[act].size(); i++) {
      if (depth[CONN[act][i]] != -1) continue;
      pa[CONN[act][i]] = act;
      depth[CONN[act][i]] = depth[act] + 1;
      Q.push(CONN[act][i]);
    }
  }
  long long md = 0;
  for (long long i = 1; i <= n; i++) md = max(depth[i], md);
  for (long long i = 1; i <= n; i++)
    if (depth[i] == md) return i;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (long long i = 0; i < n - 1; i++) {
    long long u, v;
    cin >> u >> v;
    CONN[u].push_back(v);
    CONN[v].push_back(u);
  }
  leaf1 = bfs1(arr0, 1, pa2);
  leaf2 = bfs1(arr0, leaf1, pa1);
  for (int i = 1; i <= n; i++) {
    if (CONN[i].size() == 1) leafs.push(i);
    CONNSZ[i] = CONN[i].size();
  }
  bfs1(arr1, leaf1, pa2);
  bfs1(arr2, leaf2, pa2);
  long long ans = 0;
  vector<tuple<long long, long long, long long>> fnl;
  while (!leafs.empty()) {
    long long act = leafs.front();
    leafs.pop();
    dead[act] = 1;
    if (act == leaf1 || act == leaf2) continue;
    if (arr1[act] > arr2[act]) fnl.push_back(make_tuple(leaf1, act, act));
    if (arr2[act] >= arr1[act]) fnl.push_back(make_tuple(leaf2, act, act));
    ans += max(arr1[act], arr2[act]);
    for (long long i = 0; i < CONN[act].size(); i++) {
      if (dead[CONN[act][i]]) continue;
      CONNSZ[CONN[act][i]]--;
      if (CONNSZ[CONN[act][i]] == 1) leafs.push(CONN[act][i]);
    }
  }
  ans += arr1[leaf2] * (arr1[leaf2] + 1) / 2;
  long long v = leaf2;
  while (v != leaf1) fnl.push_back(make_tuple(leaf1, v, v)), v = pa1[v];
  cout << ans << '\n';
  for (long long i = 0; i < fnl.size(); i++) {
    cout << get<0>(fnl[i]) << ' ' << get<1>(fnl[i]) << ' ' << get<2>(fnl[i])
         << '\n';
  }
}