E. Покрывай!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Ваша задача — выбрать не более $$$\lfloor\frac{n}{2}\rfloor$$$ вершин в данном графе так, чтобы каждая невыбранная вершина была смежна (другими словами, связана ребром) с хотя бы одной выбранной вершиной.

Гарантируется, что ответ существует. Если существует несколько решений, выведите любое из них.

Требуется ответить на несколько независимых запросов.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$t$$$ запросов.

В первой строке каждого запроса записаны два целых числа $$$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$$$. Гарантируется, что данных граф связен.

Гарантируется, что $$$\sum m \le 2 \cdot 10^5$$$ по всем запросам.

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

Для каждого запроса выведите две строки.

В первой строке выведите $$$k$$$ ($$$1 \le \lfloor\frac{n}{2}\rfloor$$$) — количество выбранных вершин.

Во второй строке выведите $$$k$$$ различных целых чисел $$$c_1, c_2, \dots, c_k$$$ в произвольном порядке, где $$$c_i$$$ равно номеру $$$i$$$-й выбранной вершины.

Гарантируется, что ответ всегда существует. Если существует несколько решений, выведите любое из них.

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

В первом запросе любая вершина или любая пара вершин подойдет.

Обратите внимание, что не обязательно минимизировать количество выбранных вершин. Во втором запросе двух вершин достаточно (вершины $$$2$$$ и $$$4$$$), но три так же подойдут.