28645번 - Теория Рамсея 스페셜 저지다국어

Карта для Among Us представляет собой неориентированный граф, вершины которого --- комнаты, а рёбра --- двусторонние тоннели между ними. У разработчика этой игры, Рамсея, есть теория, что карта должна удовлетворять некоторым свойствам, чтобы на ней было интересно играть.

В игре будет $k$ предателей и $l$ рядовых членов экипажа. Если в графе есть $l$-клика --- набор из $l$ вершин, каждая пара которых соединена ребром --- то члены экипажа просто распределятся между ними, и в случае убийства кого-то из них все игроки из соседних комнат незамедлительно сбегутся, обнаружат убийцу и накажут его. Такая игра будет довольно неинтересной.

С другой стороны, если в графе есть $k$-антиклика --- набор из $k$ вершин, каждая пара которых не соединена ребром --- то предатели смогут встать в её вершины, заманивать хороших игроков и их там убивать, и, скорее всего, им удастся при этом оставаться незамеченными. Такая стратегия, по мнению Рамсея, тоже сделает игру неинтересной.

Напишите программу, которая найдёт в графе $l$-клику или $k$-антиклику или определит, что их в графе нет (и тогда игра обещает быть захватывающей).

В первой строке находится четыре числа $n$, $m$, $k$, $l$, разделённых пробелами --- количество вершин и рёбер графа, а также размеры искомых антиклики и клики ($1 \le n \le 300\,000$; $0 \le m \le 300\,000$; $1 \le k, l \le \min(5, n)$).

В следующих $m$ строках находится по два целых числа $a_i, b_i$, разделённых пробелами --- концы очередного ребра графа ($1 \le a_i < b_i \le n$). Гарантируется, что все рёбра различны.

Если вы нашли набор вершин, являющийся или $k$-антикликой, или $l$-кликой, выведите номера всех этих вершин через пробел. Если же такого набора вершин нет, выведите <<-1>>.

Первый пример выглядит как пятиугольник, в котором провели все стороны, но не провели диагоналей. В нём нет ни треугольников, ни антитреугольников, поэтому ответ <<-1>>.

Во втором и третьем примере граф пуст. Во втором примере требуется либо найти антиребро, либо 4-клику вершинах. Ответом послужит любая пара различных чисел от 1 до 4. В третьем примере всё наоборот --- надо найти либо 4-антиклику, либо ребро. Так как рёбер нет, единственным правильным ответом на этот пример является набор из всех чисел от 1 до 4 (перечисленных в произвольном порядке).

В четвёртом примере дан полный граф, и корректным ответом является любая четвёрка его вершин (так как она будет его кликой). Однако набор из одной вершины всегда является как кликой, так и антикликой; следовательно, раз в примере разрешено вывести 1-антиклику, любое одновершинное множество --- также корректный ответ.