Anillos de plástico
Aunque poco a poco se van reduciendo, los anillos de plástico que se utilizan para mantener juntas las latas de refresco en grupos son una maldición para las aves y la vida marina. Confundiéndolos por alimento, muchos especímenes terminan enredándose en ellos, sufriendo de por vida las consecuencias.
Las asociaciones ecologistas llevan décadas intentando concienciar del problema. Aparte de la solución obvia de reducir su uso en las plantas de envasado, a los consumidores se nos pide que, al menos, cortemos los anillos antes de desechar el plástico en el cubo de reciclaje. De esa forma se evitarán los enredos aunque, naturalmente, se seguirá incurriendo en la contaminación causada por el propio material.
Siempre que me enfrento a un plástico de anillos, tijera en mano, me hago la misma pregunta. ¿Cuál es el menor número de cortes que tengo que hacer para eliminarlos todos?
Entrada
Cada caso de prueba comienza con un número 1 ≤ n ≤ 100, indicando cuántos puntos de unión entre diferentes tiras de plástico hay en el conjunto. A continuación viene la información de esas tiras de plástico, indicando el punto de unión inicial y final que juntan (ambos números entre 1 y n).
La lista de tiras de plástico termina con dos ceros.
Ten en cuenta que a veces alguien ha empezado el trabajo por mí y ha realizado ya algunos cortes, aunque el plástico siempre formará una única pieza.
La entrada termina con un 0.
Salida
Por cada caso de prueba el programa escribirá el menor número de cortes que tenemos que realizar para evitar que la fauna se enrede en los anillos de plástico. Los puntos de unión se consideran despreciables, por lo que únicamente se pueden cortar las tiras.
Entrada de ejemplo
4 1 2 2 1 1 3 3 1 2 4 4 2 4 3 4 3 0 0 3 1 2 2 3 0 0 0
Salida de ejemplo
5 0