| Codeforces Round 565 (Div. 3) |
|---|
| Закончено |
Задан неориентированный невзвешенный связный граф, состоящий из $$$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$$$), но три так же подойдут.
