Código acm.uva.es: 10160

  Estaciones de Servicio  

Una empresa vende ordenadores en N ciudades (3 <= N <= 35). Las ciudades son denotadas por 1, 2, ..., N. Hay rutas directas que conectan M pares de estas ciudades. La empresa decide construir estaciones de servicio en varias ciudades, de manera que para cualquier ciudad X haya una estación localizada o bien en X o en alguna ciudad que tenga una ruta directa con X.

Escribe un programa para encontrar el mínimo número de estaciones que tiene que construir la empresa, de manera que se cumpla la condición anterior.

Entrada 

La entrada consta de más de un caso de prueba del problema. Cada caso comienza con el número N de ciudades y el número M de pares de ciudades conectadas de forma directa. Los enteros N y M están en la misma línea, separados por un espacio. Cada una de las siguientes M líneas contienen un par de ciudades conectadas, un par por fila. El par consta de dos enteros que indican el número de las ciudades, separados por un espacio. La entrada con N = 0 y M = 0 indica el final de la entrada.

Salida 

Para cada caso de prueba, escribir una línea con un único número indicando el mínimo obtenido.

Ejemplo de entrada  

8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

Ejemplo de salida  

2