Теория Рамсея
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

Входные данные

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

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

Выходные данные

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

Примечание

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

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

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