## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 2346

# Back to the Future

By Bruno Junqueira Brazil

Timelimit: 1

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 ≤ 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, YN with XY). 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.

 Input Samples Output Samples 3 1 1 0 1 2 2

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cstdio>
#include <set>
#include <vector>
#define MAXN 100010
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
vector<int> grafo[MAXN];
int grau[MAXN], n, m, a, b, deletado[MAXN];
set < ii> conjunto;
int main() {
scanf("%d %d %d %d", &n, &m, &a, &b);
for (int i = 1; i  < = m; i++) {
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
grau[u]++;
grau[v]++;
}
for (int i = 1; i  < = n; i++) {
conjunto.insert(MP(grau[i], i));
}
for (int vez = 0; vez  <  n && !conjunto.empty(); vez++) {
ii candidato1 = *(conjunto.begin());
int v1 = candidato1.second, g1 = candidato1.first;
if (g1  <  a) {
// printf("%d %d 1\n",v1,g1);
conjunto.erase(candidato1);
for (int i = 0; i  <  grafo[v1].size(); i++) {
int p = grafo[v1][i];
conjunto.erase(conjunto.find(MP(grau[p], p)));
grau[p]--;
conjunto.insert(MP(grau[p], p));
}
}
if (conjunto.empty()) break;
ii candidato2 = *(conjunto.rbegin());
int v2 = candidato2.second, g2 = candidato2.first;
if ((int)conjunto.size() - g2 - 1  <  b) {
// printf("%d %d 2\n",v2,g2);
conjunto.erase(candidato2);
for (int i = 0; i  <  grafo[v2].size(); i++) {
int p = grafo[v2][i];
conjunto.erase(conjunto.find(MP(grau[p], p)));
grau[p]--;
conjunto.insert(MP(grau[p], p));
}
}
}
printf("%d\n", (int)conjunto.size());
return 0;
}
``````
Copy The Code &

Input

cmd
3 1 1 0
1 2

Output

cmd
2