|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
B - Back to the Future
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
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.
Input
The first line contains four integers $N$, $M$, $A$ and $B$, representing respectively how many different pieces of metal exist ($1 \le N \le 10^5$), how many compatibilities there are ($1 \le M \le 10^5$) and the variables $A$ and $B$ described in the problem statement ($0 \le 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 \leq X, Y \leq N$ with $X \neq Y$). There are no repeated pairs in the input.
Output
Output a line with one integer representing the size of the largest set of metals satisfying the requirements specified in the problem statement.
Sample test(s)
Input
3 1 1 0
1 2
Output
2
Input
3 1 1 1
1 2
Output
0
Input
7 12 2 2
1 2
2 3
3 1
4 5
5 6
6 4
3 4
7 1
2 7
3 7
4 7
5 7
Output
6