La estación central
En las películas de acción todo ocurre siempre en una estación de tren o metro concurrida y llena de gente. Pero las líneas de metro o tren tienen cientos de estaciones. ¿Cuál es la estación más importante de la red?
Un grupo de inteligencia ha decidido estudiar todas las redes de metro y tren del mundo y localizar en cada una de ellas la estación más importante, a la que van a llamar Estación Central.
Para decidir cuál es la estación central, primero tienen que quedarse con un subconjunto de estaciones, las estaciones importantes. Tras discutir su significado, han acordado que las estaciones importantes van a ser aquellas que pertenecen al menos a dos líneas de metro o tren distintas.
Finalmente deciden que la Estación Central será aquella de las estaciones importantes desde la cual se tarde menos en llegar a todas las demás estaciones importantes de la red, suponiendo siempre que el tiempo que se tarda en llegar de una estación a la siguiente (en cualquier línea) es de 10 minutos. Es decir, la estación central será aquella estación importante para la cual la suma de los tiempos para llegar a las demás estaciones importantes de la red es menor.
Entrada
La entrada consiste en varios casos de prueba, cada uno con varias líneas. Para cada caso de prueba, la primera línea contiene dos números enteros: el primero indica el número de estaciones en la red (N) y el segundo el número de líneas de la red (L). A continuación aparecen L líneas adicionales, cada una con información acerca de una línea de la red, en la cual se indican las estaciones que pertenecen a esa línea separadas por un espacio. Cada estación está representada por un número entero entre 1 y N. Al final de cada línea aparece un 0 que no corresponde a ninguna estación y se debe ignorar.
El número máximo de líneas de la red es de 100 y el número máximo de estaciones por línea es 100. Se garantiza que la red es conexa, que no habrá más de 200 estaciones importantes y que siempre habrá al menos una estación central.
El final de la entrada se indica con una línea con dos ceros que no se debe procesar.
Salida
Para cada red del fichero de entrada se indicará cual es el número de estación correspondiente a la estación central. En caso de haber varias estaciones que cumplan los requisitos, se indicará aquella que tenga un número más bajo.
Entrada de ejemplo
13 3 1 2 3 4 5 6 7 0 8 9 4 10 13 0 11 2 12 9 6 7 0 6 2 2 5 3 6 1 4 0 4 1 6 3 5 2 0 5 2 1 2 3 4 5 0 3 5 1 4 2 0 0 0
Salida de ejemplo
9 3 4