F1. Покрывающее дерево максимальной степени
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан неориентированный невзвешенный связный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Гарантируется, что в графе отсутствуют петли и кратные ребра.

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

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — количество вершин и ребер соответственно.

Следующие $$$m$$$ строк описывают ребра: ребро $$$i$$$ представлено в виде пары целых чисел $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$), которые означают номера вершин, соединяемых этим ребром. В заданном графе отсутствуют петли и кратные ребра, то есть для каждой пары ($$$v_i, u_i$$$) в списке ребер не существует других пар ($$$v_i, u_i$$$) или ($$$u_i, v_i$$$), также для каждой пары $$$(v_i, u_i)$$$ выполняется условие $$$v_i \ne u_i$$$.

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

Выведите $$$n-1$$$ строк, описывающих такое покрывающее дерево, что максимальная степень вершины в нем максимально возможная. Убедитесь, что ребра выводимого покрывающего дерева представляют собой подмножество ребер входных данных (порядок ребер не важен, также ребро $$$(v, u)$$$ может быть выведено как $$$(u, v)$$$).

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

Примеры
Входные данные
5 5
1 2
2 3
3 5
4 3
1 5
Выходные данные
3 5
2 1
3 2
3 4
Входные данные
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Выходные данные
4 1
1 2
1 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
Примечание

Картинка, соответствующая первому тестовому примеру:

В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине $$$3$$$, равно $$$3$$$. Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.

Картинка, соответствующая в торомутестовому примеру:

В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине $$$1$$$, равно $$$3$$$. Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.

Картинка, соответствующая третьему тестовому примеру:

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