Теорія Рамсея
Карта для "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-антикліку, будь-яка одновершинна множина - також коректна відповідь.