Задано невзвешенное дерево с n вершинами. С ним производят n - 1 операцию. Каждая из операций состоит в следующем:
- выбирается два листа в дереве;
- к ответу добавляется длина простого пути между этими листами;
- выбирается один из этих двух листов и удаляется из дерева.
До проведения операций ответ равен 0. Очевидно, что после n - 1 проведённой операции в дереве останется одна вершина.
Вам необходимо посчитать, какого максимального ответа можно добиться, если действовать оптимально, и вывести, каким образом необходимо действовать.
Выходные данные
В первой строке выведите одно целое число — максимальный ответ, которого можно достигнуть.
В следующих n - 1 строках выведите действия в порядке их совершения в формате ai, bi, ci, где ai, bi — пара листов, выбранных на текущем шаге (1 ≤ ai, bi ≤ n), ci (1 ≤ ci ≤ n, ci = ai или ci = bi) — выбранный лист, который удаляется на текущем шаге.
Посмотрите в примеры для лучшего понимания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
1 3
|
3
2 3 3
2 1 1
|
|
2
|
5
1 2
1 3
2 4
2 5
|
9
3 5 5
4 3 3
4 1 1
4 2 2
|