Карта для "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 строках находится по два целых числа a[i]
, b[i]
(1 ≤ a[i]
< b[i]
≤ n) - концы очередного ребра графа. Гарантируется, что все рёбра различны.
Если Вы нашли набор вершин, являющийся или k-антикликой, или l-кликой, выведите номера всех этих вершин через пробел. Если же такого набора вершин нет, выведите "-1".
Первый пример выглядит как пятиугольник, в котором провели все стороны, но не провели диагоналей. В нём нет ни треугольников, ни антитреугольников, поэтому ответ "-1".
Во втором и третьем примере граф пуст. Во втором примере требуется либо найти антиребро, либо 4-клику вершинах. Ответом послужит любая пара различных чисел от 1 до 4. В третьем примере всё наоборот - надо найти либо 4-антиклику, либо ребро. Так как рёбер нет, единственным правильным ответом на этот пример является набор из всех чисел от 1 до 4 (перечисленных в произвольном порядке).
В четвёртом примере дан полный граф, и корректным ответом является любая четвёрка его вершин (так как она будет его кликой). Однако набор из одной вершины всегда является как кликой, так и антикликой; следовательно, раз в примере разрешено вывести 1-антиклику, любое одновершинное множество - также корректный ответ.