Ir al contenido (saltar navegación)

Limitando los contactos

Tiempo máximo: 2,000-4,000 sMemoria máxima: 4096 KiB
Hospital de campaña durante la pandemia de gripo de 1918.

En 1918 se desató una pandemia de gripe que mató en un solo año a más de 20 millones de personas en todo el mundo. Aunque es aceptado que su origen fue en Estados Unidos la historia la recuerda como la "gripe española" porque, de entre los países a los que más afectó, España fue de los pocos que no estaba envuelto en la Primera Guerra Mundial y tanto la población como la prensa pudieron dedicar toda la atención a su evolución.

Cuentan las crónicas de entonces que los gobernantes españoles, aconsejados por los expertos en sanidad, intentaron limitar los contactos personales para evitar contagios. Se pusieron de moda palabras como confinamiento perimetral, distanciamiento socialtoque de queda. Sin embargo algunas de las directrices emitidas por los políticos fueron declaradas anticonstitucionales en los tribunales porque, decían, no se podía limitar "alegremente" la movilidad de la población.

Parece ser que en una montañosa región del Norte de España, sin embargo, tuvieron una brillante idea para limitar el tamaño de las reuniones de vecinos sin problemas jurídicos. La comarca entera estaba formada por casas distribuidas por toda la falda de la montaña unidas por carreteras rudimentarias. Lo único que tuvieron que hacer fue convertirlas en calzadas de un único sentido. De esa forma los vecinos no vieron limitada por ley su movilidad pero si salían de sus casas quizá no podrían volver...

Gracias a ese pequeño cambio, el número máximo de vecinos que podían reunirse simultáneamente en un mismo sitio se redujo mucho, pues nadie acudía a una reunión si luego no iba a tener camino de vuelta a casa.

Entrada

La entrada está compuesta por distintos casos de prueba, cada uno ocupando varias líneas.

Cada caso comienza con un número n que indica el número de casas que hay distribuidas en la comarca (1 ≤ n ≤ 1000) seguido de una o más líneas con la descripción del mapa de carreteras, que no tendrá más de 100.000 enlaces.

Cada una de las líneas del mapa comienza con un número de casa (entre 1 y n) seguido del número de carreteras (de un único sentido) que salen de ella. Le siguen a eso los destinos de cada carretera.

Tras la definición completa del mapa viene una línea con un 0.

Salida

Para cada caso de prueba se escribirá una línea con un único entero indicando el número de vecinos que pueden reunirse como mucho en un mismo sitio manteniendo la condición de que todos ellos podrán después volver a sus casas.

Entrada de ejemplo

4
1 1 3
3 1 2
2 2 1 4
0
3
1 1 2
0

Salida de ejemplo

3
1