F. Максимально не похожее дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево с $$$n$$$ вершинами с корнем в вершине $$$1$$$, обозначим его за $$$G$$$. Также обозначим за $$$P(G)$$$ мультимножество поддеревьев всех вершин дерева $$$G$$$. Вам надо найти дерево $$$G'$$$ размера $$$n$$$ с корнем в вершине $$$1$$$ такое, что количество поддеревьев в $$$P(G')$$$ к которым есть изоморфные в $$$P(G)$$$ было минимально.

Поддерево вершины $$$v$$$ - это граф, который содержит все вершины, для которых вершина $$$v$$$ лежит на пути от корня дерева до нее самой, а так же все ребра между этими вершинами.

Два корневых дерева считаются изоморфными если можно так перенумеровать вершины одного из них, чтобы оно стало равно второму, при этом корень первого дерева должен получить номер корня второго дерева.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) - количество вершин в дереве $$$G$$$. Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$ $$$(1 \leq a,b \leq n)$$$, означающие, что между вершинами $$$a$$$ и $$$b$$$ в дереве есть ребро.

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

Выведите $$$n-1$$$ строку, каждая строка содержит два числа $$$a$$$, $$$b$$$ $$$(1 \leq a,b \leq n)$$$ - рёбра дерева $$$G'$$$. Если существует несколько оптимальных ответов, выведите любой.

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