Вам дан неориентированный граф с \(n\) вершинами и \(m\) ребрами. Также вам дано целое число \(k\).
Найдите либо клику размера \(k\), либо непустое подмножество вершин такое, что каждая вершина этого подмножества имеет хотя бы \(k\) соседей в этом подмножестве. Если ни одной такой клики или такого подмножества не существует, сообщите об этом.
Подмножество вершин называется кликой размера \(k\), если его размер равен \(k\) и существуют ребра между всеми парами вершин этого подмножества. Вершина называется соседом другой вершины, если существует ребро между ними.
Выходные данные
Для каждого набора входных данных:
Если вы нашли подмножество вершин, в котором каждая вершина имеет хотя бы \(k\) соседей из этого подмножества, в первой строке выведите \(1\) и размер этого подмножества. Во второй строке выведите все вершины этого подмножества в любом порядке.
Если вы нашли клику размера \(k\), выведите в первой строке \(2\) и во второй строке все вершины клики в любом порядке.
Если не существует ни одной необходимой клики или подмножества выведите \(-1\).
Если существует несколько возможных ответов выведите любой.
Примечание
В первом наборе входных данных: подмножество \(\{1, 2, 3, 4\}\) является кликой размера \(4\).
Во втором наборе входных данных: степень каждой вершины изначального графа хотя бы \(3\). Поэтому множество всех вершин является правильным ответом.
В третьем наборе входных данных: не существует клик размера \(4\) и необходимых подмножеств, поэтому ответ \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|