Codeforces Round 544 (Div. 3) |
---|
Закончено |
Задан неориентированный невзвешенный связный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Гарантируется, что в графе отсутствуют петли и кратные ребра.
Ваша задача — найти любое такое покрывающее дерево этого графа, что максимальная степень вершины в нем максимально возможная. Напомним, что степень вершины — это количество ребер, инцидентных ей.
Первая строка входных данных содержит два целых числа $$$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$$$.
Выведите $$$n-1$$$ строк, описывающих такое покрывающее дерево, что максимальная степень вершины в нем максимально возможная. Убедитесь, что ребра выводимого покрывающего дерева представляют собой подмножество ребер входных данных (порядок ребер не важен, также ребро $$$(v, u)$$$ может быть выведено как $$$(u, v)$$$).
Если существует несколько возможных ответов, выведите любой.
5 5 1 2 2 3 3 5 4 3 1 5
3 5 2 1 3 2 3 4
4 6 1 2 1 3 1 4 2 3 2 4 3 4
4 1 1 2 1 3
8 9 1 2 2 3 2 5 1 6 3 4 6 5 4 5 2 7 5 8
3 2 2 5 8 5 6 1 2 7 1 2 3 4
Картинка, соответствующая первому тестовому примеру:
В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине $$$3$$$, равно $$$3$$$. Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.
Картинка, соответствующая в торомутестовому примеру:
В этом тестовом примере количество ребер покрывающего дерева, инцидентных вершине $$$1$$$, равно $$$3$$$. Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше.
Картинка, соответствующая третьему тестовому примеру:
В этом тестовом примере количество ребер покрывающего дереева, инцидентных вершине $$$2$$$, равно $$$4$$$. Это максимально возможная степень вершины в покрывающем дереве. Легко заметить, что мы не можем получить ответ лучше. Но так как этот тестовый пример симметричный, мы можем выбрать почти тоже самое покрывающее дерево, только с вершиной $$$5$$$ вместо вершины $$$2$$$.
Название |
---|