Como el rosario de la aurora
En mi oficina vamos a terminar todos como el rosario de la aurora. A lo largo de los años se han ido produciendo confrontaciones entre compañeros (que si uno se ha llevado la tartera de otro con sus macarrones, que si una pone el termostato muy alto, que si otro le ha quitado la novia al uno, etc.) que han ido construyendo una intrincada red de enemistad. Las relaciones de amistad y odio se rigen por las siguientes propiedades:
- Reflexividad de la amistad: Toda persona es amiga de sí misma.
- Antirreflexividad de la enemistad: Ninguna persona es enemiga de sí misma.
- Simetría: Si A es amigo de B, entonces B es amigo de A. Similarmente, si A es enemigo de B, entonces B es enemigo de A.
- Transitividad de la amistad: Si A es amigo de B, los amigos de B son también amigos de A y los enemigos de B son también enemigos de A.
- Anti-transitividad de la enemistad: Si A es enemigo de B, los amigos de B son enemigos de A y los enemigos de B son amigos de A.
La Señora Luisa, la más antigua y cotilla del lugar, se acuerda de todas las peleas producidas en la oficina a lo largo de la historia.
El mes próximo es el cumpleaños del jefe y me han encargado que le organice una fiesta. Como le encanta que le hagan la pelota, tengo que conseguir que venga el mayor número de personas, aunque el local donde se celebrará la fiesta tiene un aforo que no podremos superar. Debido a las enemistades, sé que cualquiera en la oficina solamente aceptará la invitación si todos sus amigos son también invitados y no se invita a ninguno de sus enemigos. ¿Me ayudas a averiguar cuál es el máximo número de personas que puedo invitar de tal forma que todos acepten la invitación?
Entrada
La entrada consta de diversos casos de prueba. Para cada caso, la primera línea contiene tres números: el número N de personas en la oficina (1 ≤ N ≤ 1.000); el número P de peleas (entre dos personas) que la señora Luisa recuerda (0 ≤ P ≤ 10.000); y el aforo A del local donde celebraremos la fiesta (1 ≤ A ≤ 1.000). A continuación aparecen P líneas, cada una con dos enteros entre 1 y N que representan las personas que se enfrentaron. Las relaciones de amistad y enemistad inducidas por estas peleas cumplen las propiedades arriba indicadas.
Salida
Para cada caso de prueba se escribirá en una línea independiente el número máximo de personas que puedo invitar con la seguridad de que todas acudirán a la fiesta y de que no se supera el aforo del local (la plaza para el jefe está obviamente reservada y ya ha sido descontada del aforo).
Entrada de ejemplo
9 6 7 1 3 2 1 1 4 5 6 6 7 7 8
Salida de ejemplo
6