Codeforces Round 684 (Div. 1) |
---|
Закончено |
Вам дан неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Также вам дано целое число $$$k$$$.
Найдите либо клику размера $$$k$$$, либо непустое подмножество вершин такое, что каждая вершина этого подмножества имеет хотя бы $$$k$$$ соседей в этом подмножестве. Если ни одной такой клики или такого подмножества не существует, сообщите об этом.
Подмножество вершин называется кликой размера $$$k$$$, если его размер равен $$$k$$$ и существуют ребра между всеми парами вершин этого подмножества. Вершина называется соседом другой вершины, если существует ребро между ними.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. В следующей строке находится описание наборов входных данных.
В первой строке описания каждого набора входных данных находится три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n, m, k \leq 10^5$$$, $$$k \leq n$$$).
Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u, v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$, обозначающих ребро между вершинами $$$u$$$ и $$$v$$$.
Гарантируется, что в графе нет петель и кратных ребер. Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных:
Если вы нашли подмножество вершин, в котором каждая вершина имеет хотя бы $$$k$$$ соседей из этого подмножества, в первой строке выведите $$$1$$$ и размер этого подмножества. Во второй строке выведите все вершины этого подмножества в любом порядке.
Если вы нашли клику размера $$$k$$$, выведите в первой строке $$$2$$$ и во второй строке все вершины клики в любом порядке.
Если не существует ни одной необходимой клики или подмножества выведите $$$-1$$$.
Если существует несколько возможных ответов выведите любой.
3 5 9 4 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 10 15 3 1 2 2 3 3 4 4 5 5 1 1 7 2 8 3 9 4 10 5 6 7 10 10 8 8 6 6 9 9 7 4 5 4 1 2 2 3 3 4 4 1 1 3
2 4 1 2 3 1 10 1 2 3 4 5 6 7 8 9 10 -1
В первом наборе входных данных: подмножество $$$\{1, 2, 3, 4\}$$$ является кликой размера $$$4$$$.
Во втором наборе входных данных: степень каждой вершины изначального графа хотя бы $$$3$$$. Поэтому множество всех вершин является правильным ответом.
В третьем наборе входных данных: не существует клик размера $$$4$$$ и необходимых подмножеств, поэтому ответ $$$-1$$$.
Название |
---|