B. Задача о подмножестве графа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф с $$$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$$$.