Ramsey Theory

Time limit2sMemory limit1024 MB

Summary

Given a graph, find a clique of size l or an anticlique of size k, or report that neither exists.

Level: Medium6 of 10
Topics: Graph, Backtracking, Brute force
Solved: No attempts yet

Problem

The map for Among Us is an undirected graph. Vertices are rooms, and edges are two-way tunnels between them. The game developer Ramsey believes a map must satisfy certain properties to make the game interesting.

The game has $k$ traitors and $l$ regular crew members. If the graph contains an $l$ -clique, meaning a set of $l$ vertices where every pair is joined by an edge, the crew members are spread across those vertices. If one of them is killed, all players in adjacent rooms rush over at once, find the killer, and punish them. Such a game is quite boring.

On the other hand, if the graph contains a $k$ -anticlique, meaning a set of $k$ vertices where no pair is joined by an edge, the traitors can stand on those vertices, lure good players there, and kill them, and they will likely go unnoticed. Ramsey believes this strategy also makes the game boring.

Write a program that finds an $l$ -clique or a $k$ -anticlique in the graph, or determines that neither exists. In that case, Ramsey promises the game will be exciting.

Input

The first line contains four integers $n$ , $m$ , $k$ , $l$ , separated by spaces: the number of vertices, the number of edges, and the sizes of the anticlique and the clique to find ( $1 \le n \le 300000$ ; $0 \le m \le 300000$ ; $1 \le k, l \le \min(5, n)$ ).

Each of the next $m$ lines contains two integers $a_i, b_i$ , separated by a space: the endpoints of an edge ( $1 \le a_i < b_i \le n$ ). All edges are distinct.

Output

If you find a set of vertices that is either a $k$ -anticlique or an $l$ -clique, print the numbers of all these vertices separated by spaces. If no such set exists, print $-1$ .

Hints

The first sample is a pentagon with all five sides drawn and no diagonals. It has no triangles and no anti-triangles, so the answer is $-1$ .

The second and third samples have an empty graph. In the second sample you need either an anti-edge or a 4-clique. Any two distinct numbers from 1 to 4 is a correct answer. The third sample is the reverse: you need either a 4-anticlique or an edge. Since there are no edges, the only correct answer is the set of all numbers from 1 to 4, listed in any order.

The fourth sample is a complete graph, so any four of its vertices form a clique and are a correct answer. A single vertex is always both a clique and an anticlique. Since the sample allows a 1-anticlique, any one-vertex set is also a correct answer.

Examples4

Example 1
Input
```
5 5 3 3
1 2
2 3
3 4
4 5
1 5
```
Expected output
```
-1
```
Example 2
Input
```
4 0 2 4
```
Expected output
```
1 2
```
Example 3
Input
```
4 0 4 2
```
Expected output
```
1 2 3 4
```

Example 4

Input

Expected output