C. Переподвешивание дерева
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево размера n и разрешается выполнить не более 2n операций над ним. Операция заключается в выборе трех вершин x, y, y', удалении ребра (x, y) и добавлении ребра (x, y'). Операцию x, y, y' можно выполнить в случае, если выполнены все условия:

  1. Ребро (x, y) присутствует в дереве.
  2. После операции граф останется деревом.
  3. При удалении ребра (x, y) дерево распадается на две компоненты связности. Обозначим множество вершин в одной компоненте с вершиной x множеством Vx, а в одной компоненте с вершиной y — множеством Vy. Тогда должно выполняться условие |Vx| > |Vy|, т.е. размер компоненты с x должен быть строго больше размера компоненты с y.

Вам требуется минимизировать сумму квадратов расстояний между всеми парами вершин в итоговом дереве, полученном после не более чем 2n операций, а также предоставить последовательность операций, с помощью которых можно получить итоговое дерево из исходного.

Обратите внимание, что минимизировать количество операций не нужно. Нужно минимизировать исключительно сумму квадратов расстояний.

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

Первая строка входных данных содержит целое число n (1 ≤ n ≤ 2·105) — количество вершин в дереве.

Следующие n - 1 строки входных данных содержат пары целых чисел a и b (1 ≤ a, b ≤ n, a ≠ b) — описания рёбер. Гарантируется, что данные ребра образуют дерево.

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

В первой строке выведите число k (0 ≤ k ≤ 2n) — количество операций, которые нужно провести, чтобы минимизировать сумму квадратов расстояний между различными парами вершин.

В следующих k строках выведите по три целых числа x, y, y' — номера вершин, участвующих в очередной операции.

Операции, в которых y = y', разрешены (хоть ничего и не меняют), если выполнены условия операции.

Если возможных ответов несколько, выведите любой из них.

Примеры
Входные данные
3
3 2
1 3
Выходные данные
0
Входные данные
7
1 2
2 3
3 4
4 5
5 6
6 7
Выходные данные
2
4 3 2
4 5 6
Примечание

Иллюстрация изменений графа во втором примере из условия. Темным обозначены ребра после операции, пунктиром — до.