70. Regreso al futuro
Autor: Bruno Junqueira
Limite de tiempo : 1 seg. Total runs : 1 Aceptados : 1
El doctor Emmet está trabajando en un dispositivo más seguro para viajar en el tiempo. Reunió N diferentes y raras piezas de metal. Cada pieza puede ser compatible con algunas otras piezas diferentes. Tiene una lista completa con M pares distintos de metales compatibles. Cualquier par de metales que no esté en la lista es incompatible.
Para que el dispositivo funcione, debe elegir un conjunto de metales de manera que cada uno de ellos sea compatible con al menos A otros en ese conjunto. Sin embargo, para preservar cierto equilibrio, también deben ser incompatibles con al menos B otros en ese conjunto.
Más metales significa más energía y un dispositivo más seguro. Es por eso que el doctor Emmet necesita su ayuda, quiere saber el tamaño del conjunto más grande que puede elegir que cumpla con estos criterios.
Entrada
La primera línea contiene cuatro enteros N , M , A y B , que representan, respectivamente, cuántas piezas diferentes de metal existen (1 ≤ N ≤ 10 5 ), cuántas compatibilidades hay (1 ≤ M ≤ 10 5) y las variables A y B descrito en la declaración del problema (0 ≤ A , B <N). Los diferentes metales se numeran convenientemente de 1 a N . Cada una de las siguientes líneas M contiene dos enteros X e Y correspondientes a un par de metales compatibles (1 ≤X , Y ≤ N con X ≠ Y ). No hay pares repetidos en la entrada.
Salida
Imprima una línea con un número entero que represente el tamaño del conjunto más grande de metales que satisfaga los requisitos especificados en la declaración del problema.
Ejemplo Entrada
3 1 1 0
1 2
3 1 1 1
1 2
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
Ejemplo Salida
2
0
6