Олимпиадный тренинг

Задача . F2. Покрывающее дерево с одной фиксированной степенью

Задача

Темы: графы жадные алгоритмы Конструктив поиск в глубину и подобное снм *1900

Задан неориентированный невзвешенный связный граф, состоящий из $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)$).

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

Примечание

Картинка, соответствующая первому и второму тестовым примерам: $\text{[math]}$