Дано дерево с \(n\) вершинами с корнем в вершине \(1\), обозначим его за \(G\). Также обозначим за \(P(G)\) мультимножество поддеревьев всех вершин дерева \(G\). Вам надо найти дерево \(G'\) размера \(n\) с корнем в вершине \(1\) такое, что количество поддеревьев в \(P(G')\) к которым есть изоморфные в \(P(G)\) было минимально.
Поддерево вершины \(v\) - это граф, который содержит все вершины, для которых вершина \(v\) лежит на пути от корня дерева до нее самой, а так же все ребра между этими вершинами.
Два корневых дерева считаются изоморфными если можно так перенумеровать вершины одного из них, чтобы оно стало равно второму, при этом корень первого дерева должен получить номер корня второго дерева.
Выходные данные
Выведите \(n-1\) строку, каждая строка содержит два числа \(a\), \(b\) \((1 \leq a,b \leq n)\) - рёбра дерева \(G'\). Если существует несколько оптимальных ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
1 2
|
|
2
|
3
1 2
1 3
|
1 2
2 3
|
|
3
|
4
1 2
1 3
3 4
|
1 2
2 3
3 4
|