Теория Рамсея
Теория Рамсея
Карта для "Among Us" представляет собой неориентированный граф, вершины которого - комнаты, а рёбра - двусторонние тоннели между ними. У разработчика этой игры, Рамсея, есть теория, что карта должна удовлетворять некоторым свойствам, чтобы на ней было интересно играть.
В игре будет k предателей и l рядовых членов экипажа. Если в графе есть l-клика - набор из l вершин, каждая пара которых соединена ребром - то члены экипажа просто распределятся между ними, и в случае убийства кого-то из них все игроки из соседних комнат незамедлительно сбегутся, обнаружат убийцу и накажут его. Такая игра будет довольно неинтересной.
С другой стороны, если в графе есть k-антиклика - набор из k вершин, каждая пара которых не соединена ребром - то предатели смогут встать в её вершины, заманивать хороших игроков и их там убивать, и, скорее всего, им удастся при этом оставаться незамеченными. Такая стратегия, по мнению Рамсея, тоже сделает игру неинтересной.
Напишите программу, которая найдёт в графе l-клику или k-антиклику или определит, что их в графе нет (и тогда игра обещает быть захватывающей).
Входные данные
В первой строке находится четыре числа n, m, k, l (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 300 000, 1 ≤ k, l ≤ min(5, n)) - количество вершин и рёбер графа, а также размеры искомых антиклики и клики.
В следующих m строках находится по два целых числа ai
, bi
(1 ≤ ai
< bi
≤ n) - концы очередного ребра графа. Гарантируется, что все рёбра различны.
Выходные данные
Если Вы нашли набор вершин, являющийся или k-антикликой, или l-кликой, выведите номера всех этих вершин через пробел. Если же такого набора вершин нет, выведите "-1".
Замечание
Первый пример выглядит как пятиугольник, в котором провели все стороны, но не провели диагоналей. В нём нет ни треугольников, ни антитреугольников, поэтому ответ "-1".
Во втором и третьем примере граф пуст. Во втором примере требуется либо найти антиребро, либо 4-клику вершинах. Ответом послужит любая пара различных чисел от 1 до 4. В третьем примере всё наоборот - надо найти либо 4-антиклику, либо ребро. Так как рёбер нет, единственным правильным ответом на этот пример является набор из всех чисел от 1 до 4 (перечисленных в произвольном порядке).
В четвёртом примере дан полный граф, и корректным ответом является любая четвёрка его вершин (так как она будет его кликой). Однако набор из одной вершины всегда является как кликой, так и антикликой; следовательно, раз в примере разрешено вывести 1-антиклику, любое одновершинное множество - также корректный ответ.
5 5 3 3 1 2 2 3 3 4 4 5 1 5
-1
4 0 2 4
1 2
4 0 4 2
1 2 3 4
5 10 1 4 1 2 2 3 3 4 4 5 1 3 2 4 3 5 1 4 2 5 1 5
1