Задан неориентированный невзвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер. Гарантируется, что в данном графе нет петель и кратных ребер.
Ваша задача — выбрать не более \(\lfloor\frac{n}{2}\rfloor\) вершин в данном графе так, чтобы каждая невыбранная вершина была смежна (другими словами, связана ребром) с хотя бы одной выбранной вершиной.
Гарантируется, что ответ существует. Если существует несколько решений, выведите любое из них.
Требуется ответить на несколько независимых запросов.
Выходные данные
Для каждого запроса выведите две строки.
В первой строке выведите \(k\) (\(1 \le \lfloor\frac{n}{2}\rfloor\)) — количество выбранных вершин.
Во второй строке выведите \(k\) различных целых чисел \(c_1, c_2, \dots, c_k\) в произвольном порядке, где \(c_i\) равно номеру \(i\)-й выбранной вершины.
Гарантируется, что ответ всегда существует. Если существует несколько решений, выведите любое из них.
Примечание
В первом запросе любая вершина или любая пара вершин подойдет.
Обратите внимание, что не обязательно минимизировать количество выбранных вершин. Во втором запросе двух вершин достаточно (вершины \(2\) и \(4\)), но три так же подойдут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|