Back to the Future
By Bruno Junqueira 
Brazil
By Bruno Junqueira Brazil
Doctor Emmet is working on a safer device to travel in time. He gathered N different and rare pieces of metal. Each piece may be compatible with some other different pieces. He has a complete list with M distinct pairs of compatible metals. Any pair of metals that is not on the list is incompatible.
In order for the device to work, he must choose a set of metals such that each of them is compatible with at least A others in that set. However, in order to preserve some balance, they must also be incompatible with at least B others in that set.
More metals mean more energy and a safer device. This is why Doctor Emmet needs your help, he wants to know the size of the largest set he can choose that meets these criteria.
The first line contains four integers N, M, A and B, representing respectively how many different pieces of metal exist (1 ≤ N ≤ 105), how many compatibilities there are (1 ≤ M ≤ 105) and the variables A and B described in the problem statement (0 ≤ A,B < N). The different metals are conveniently numbered from 1 to N. Each of the following M lines contains two integers X and Y corresponding to a pair of compatible metals (1 ≤ X, Y ≤ N with X ≠Y). There are no repeated pairs in the input.
Output a line with one integer representing the size of the largest set of metals satisfying the requirements specified in the problem statement.
| Input Samples | Output Samples |
|
3 1 1 0 |
2 |
|
3 1 1 1 |
0 |
|
7 12 2 2 |
6 |