Islas
Problem
Un estado disperso en las islas de Oceanía decidió crear una red de carreteras (o mejor dicho, puentes). Cada puente se puede navegar en ambas direcciones. Se ha desarrollado un plan secuencial para la construcción de puentes y se sabe que después de la construcción de todos los puentes será posible conducir sobre ellos de una isla a otra (quizás a través de algunas islas intermedias
Sin embargo, este momento puede llegar antes de que se construyan todos los puentes. Debe determinar una cantidad mínima de puentes, después de la construcción de los cuales (en el orden determinado por el plan), será posible llegar de cualquier isla a cualquier otra.
Entrada
La primera línea contiene dos números: el número de islas N (1≤N≤10000) y el número de puentes en el plano M (1≤M≤50000). Luego están las líneas M, cada una con dos números x e y (1≤x,y≤N) - los números de las ciudades que están conectadas por el siguiente puente en el plan.
Salida
El programa debe generar un solo número: la cantidad mínima de puentes construidos, después de lo cual será posible llegar de cualquier isla a cualquier otra.
| Entrada |
Salida |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |