F. Разрушение дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано невзвешенное дерево с n вершинами. С ним производят n - 1 операцию. Каждая из операций состоит в следующем:

  1. выбирается два листа в дереве;
  2. к ответу добавляется длина простого пути между этими листами;
  3. выбирается один из этих двух листов и удаляется из дерева.

До проведения операций ответ равен 0. Очевидно, что после n - 1 проведённой операции в дереве останется одна вершина.

Вам необходимо посчитать, какого максимального ответа можно добиться, если действовать оптимально, и вывести, каким образом необходимо действовать.

Входные данные

В первой строке задано одно целое число n (2 ≤ n ≤ 2·105) — количество вершин в дереве.

В следующих n - 1 строках заданы рёбра дерева в формате ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Гарантируется, что заданный граф является деревом.

Выходные данные

В первой строке выведите одно целое число — максимальный ответ, которого можно достигнуть.

В следующих n - 1 строках выведите действия в порядке их совершения в формате ai, bi, ci, где ai, bi — пара листов, выбранных на текущем шаге (1 ≤ ai, bi ≤ n), ci (1 ≤ ci ≤ n, ci = ai или ci = bi) — выбранный лист, который удаляется на текущем шаге.

Посмотрите в примеры для лучшего понимания.

Примеры
Входные данные
3
1 2
1 3
Выходные данные
3
2 3 3
2 1 1
Входные данные
5
1 2
1 3
2 4
2 5
Выходные данные
9
3 5 5
4 3 3
4 1 1
4 2 2