Вам дано дерево размера n и разрешается выполнить не более 2n операций над ним. Операция заключается в выборе трех вершин x, y, y', удалении ребра (x, y) и добавлении ребра (x, y'). Операцию x, y, y' можно выполнить в случае, если выполнены все условия:
- Ребро (x, y) присутствует в дереве.
- После операции граф останется деревом.
- При удалении ребра (x, y) дерево распадается на две компоненты связности. Обозначим множество вершин в одной компоненте с вершиной x множеством Vx, а в одной компоненте с вершиной y — множеством Vy. Тогда должно выполняться условие |Vx| > |Vy|, т.е. размер компоненты с x должен быть строго больше размера компоненты с y.
Вам требуется минимизировать сумму квадратов расстояний между всеми парами вершин в итоговом дереве, полученном после не более чем 2n операций, а также предоставить последовательность операций, с помощью которых можно получить итоговое дерево из исходного.
Обратите внимание, что минимизировать количество операций не нужно. Нужно минимизировать исключительно сумму квадратов расстояний.
Выходные данные
В первой строке выведите число k (0 ≤ k ≤ 2n) — количество операций, которые нужно провести, чтобы минимизировать сумму квадратов расстояний между различными парами вершин.
В следующих k строках выведите по три целых числа x, y, y' — номера вершин, участвующих в очередной операции.
Операции, в которых y = y', разрешены (хоть ничего и не меняют), если выполнены условия операции.
Если возможных ответов несколько, выведите любой из них.
Примечание
Иллюстрация изменений графа во втором примере из условия. Темным обозначены ребра после операции, пунктиром — до.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 3
|
0
|
|
2
|
7
1 2
2 3
3 4
4 5
5 6
6 7
|
2
4 3 2
4 5 6
|