Задан неориентированный невзвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер. Гарантируется, что в графе отсутствуют петли и кратные ребра.
Ваша задача — найти любое такое покрывающее дерево этого графа, что максимальная степень вершины в нем максимально возможная. Напомним, что степень вершины — это количество ребер, инцидентных ей.
Выходные данные
Выведите \(n-1\) строк, описывающих такое покрывающее дерево, что максимальная степень вершины в нем максимально возможная. Убедитесь, что ребра выводимого покрывающего дерева представляют собой подмножество ребер входных данных (порядок ребер не важен, также ребро \((v, u)\) может быть выведено как \((u, v)\)).
Если существует несколько возможных ответов, выведите любой.
Примечание
Картинка, соответствующая первому тестовому примеру: 
В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине \(3\), равно \(3\). Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.
Картинка, соответствующая в торомутестовому примеру: 
В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине \(1\), равно \(3\). Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.
Картинка, соответствующая третьему тестовому примеру: 
В этом тестовом примере количество ребер покрывающего дереева, инцидентных вершине \(2\), равно \(4\). Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше. Но так как этот тестовый пример симметричный, мы можем выбрать почти тоже самое покрывающее дерево, только с вершиной \(5\) вместо вершины \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 2
2 3
3 5
4 3
1 5
|
3 5
2 1
3 2
3 4
|
|
2
|
4 6
1 2
1 3
1 4
2 3
2 4
3 4
|
4 1
1 2
1 3
|
|
3
|
8 9
1 2
2 3
2 5
1 6
3 4
6 5
4 5
2 7
5 8
|
3 2
2 5
8 5
6 1
2 7
1 2
3 4
|