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

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

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

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

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

Следующие $$$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$$$.

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

Если не существует покрывающего дерева, удовлетворяющего условию задачи выведите «NO» в первой строке.

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

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

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

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

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