램지 이론

Among Us 게임의 맵은 무방향 그래프입니다. 정점은 방을, 간선은 방 사이를 잇는 양방향 터널을 뜻합니다. 게임 개발자 램지는 게임이 재미있으려면 맵이 특정 성질을 만족해야 한다고 생각합니다.

게임에는 $k$명의 배신자와 $l$명의 일반 승무원이 있습니다. 그래프에 $l$-클리크가 있으면, 즉 정점 $l$개로 이루어진 집합의 모든 쌍이 간선으로 연결되어 있으면, 승무원들은 그 정점들에 나뉘어 배치됩니다. 그중 누군가가 살해되면 인접한 방의 플레이어들이 즉시 몰려와 살인자를 찾아 벌을 줍니다. 이런 게임은 아주 재미없습니다.

반대로 그래프에 $k$-안티클리크가 있으면, 즉 정점 $k$개로 이루어진 집합의 어떤 쌍도 간선으로 연결되어 있지 않으면, 배신자들은 그 정점에 서서 선량한 플레이어를 유인해 살해할 수 있고, 대개 들키지 않습니다. 램지는 이 전략도 게임을 재미없게 만든다고 봅니다.

그래프에서 $l$-클리크 또는 $k$-안티클리크를 찾거나, 둘 다 없다고 판정하는 프로그램을 작성하세요. 둘 다 없다면 램지의 말대로 게임은 흥미진진할 것으로 기대됩니다.

첫 줄에 정점 수 $n$, 간선 수 $m$, 찾을 안티클리크의 크기 $k$, 클리크의 크기 $l$이 공백으로 구분되어 주어집니다 ($1 \le n \le 300000$; $0 \le m \le 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$을 출력합니다.

첫 번째 예제는 다섯 변을 모두 잇고 대각선은 긋지 않은 오각형입니다. 삼각형도 안티삼각형도 없으므로 답은 $-1$입니다.

두 번째와 세 번째 예제에서는 그래프에 간선이 없습니다. 두 번째 예제에서는 반간선 또는 4-클리크를 찾아야 합니다. 1부터 4까지 서로 다른 두 수이면 어떤 쌍이든 정답입니다. 세 번째 예제는 반대입니다. 4-안티클리크 또는 간선을 찾아야 합니다. 간선이 없으므로 정답은 1부터 4까지의 수 전부로 이루어진 집합뿐이며, 나열 순서는 상관없습니다.

네 번째 예제는 완전 그래프이므로, 정점 네 개를 고르면 모두 클리크가 되어 정답입니다. 정점 하나로 이루어진 집합은 클리크이면서 안티클리크입니다. 이 예제에서는 1-안티클리크 출력이 허용되므로, 정점 하나로 이루어진 집합도 정답입니다.