시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB94544554.217%

## 문제

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.

## 예제 입력 1

3 1 1 0
1 2


## 예제 출력 1

2


## 예제 입력 2

3 1 1 1
1 2


## 예제 출력 2

0


## 예제 입력 3

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


## 예제 출력 3

6


## 출처

• 문제를 만든 사람: Bruno Junqueira Adami