Archipiélago P31958

Un archipiélago está constituído por n islas, algunas de las cuales están conectadas por puentes bidireccionales. Se sabe que hay como mucho un camino entre cada par de islas. Se quieren construir hospitales de manera que nadie tenga que cruzar más de un puente para llegar a un hospital. ¿Cuál es el mínimo número de hospitales necesarios?

Entrada

La entrada consiste en varios casos, cada uno con n y el número de puentes p, seguidos de p pares x y, con x ≠ y, con las islas conectadas por cada puente. Suponed 1 ≤ n ≤ 10⁵, 0 ≤ p < n, que las islas se numeran desde 0, y que no hay más de un puente entre dos islas.

Salida

Para cada caso, escribid el mínimo número de hospitales.

Puntuación

• Test-1:   Entradas con n ≤ 8.  18 Puntos 

• Test-2:   Entradas con n ≤ 100.  27 Puntos 

• Test-3:   Entradas de todo tipo.  55 Puntos