Back to the Future

Time limit2sMemory limit512 MB

Summary

Given a graph of compatible pairs, find the largest vertex subset where each chosen vertex has at least A neighbors and at least B non-neighbors inside the subset.

Level: Hard8 of 10
Topics: Graph, Greedy, Implementation, Queue
Solved: No attempts yet

Problem

Doctor Emmet is building a safer time travel device. He has collected $N$ different rare pieces of metal. Some pairs of pieces are compatible with each other. He keeps a list of all $M$ compatible pairs, and any pair that is not on the list is incompatible.

For the device to work, he must choose a set of metals. Inside that set, every chosen piece has to be compatible with at least $A$ other chosen pieces. To keep the device balanced, every chosen piece also has to be incompatible with at least $B$ other chosen pieces.

More metal means more energy and a safer device. Find the size of the largest set that satisfies both requirements.

Input

The first line contains four integers $N$ , $M$ , $A$ and $B$ separated by spaces. $N$ is the number of metal pieces ( $1 \le N \le 10^5$ ), $M$ is the number of compatible pairs ( $1 \le M \le 10^5$ ), and $A$ and $B$ are the two values described above ( $0 \le A, B < N$ ). The metals are numbered from $1$ to $N$ .

Each of the next $M$ lines contains two integers $X$ and $Y$ describing a compatible pair ( $1 \le X, Y \le N$ , $X \ne Y$ ). No pair is given twice.

Output

Print, on one line, the size of the largest set of metals that satisfies both requirements. If no such set exists, print $0$ .

Examples5

Example 1
Input
```
3 1 1 0
1 2
```
Expected output
```
2
```
Example 2
Input
```
3 1 1 1
1 2
```
Expected output
```
0
```

Example 3

Input

Expected output

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

Example 5

Input

Expected output