Карта для 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-антиклику, любое одновершинное множество — также корректный ответ.