| Coding Cup TecNM 2025 |
|---|
| Закончено |
¡Por fin! Estás a semanas de graduarte y solo te falta terminar tus residencias profesionales en TecNM Games, una compañía de creación de videojuegos muy famosa fundada por tus héroes de la programación competitiva y egresados del TecNM. Una vez graduado serás muy feliz, ¿verdad? ¡¿VERDAD?!
Bueno, que se preocupe de eso tu yo del futuro, ahorita hay que entregar tu proyecto final de la residencia, pero revisándolo, te has dado cuenta de que la dificultad del videojuego en el que trabajas puede ser mucho más baja de lo esperado tomando las rutas correctas.
En el videojuego, empiezas en el mundo 1 y, dependiendo de las rutas que tomes, te vas desplazando entre mundos hasta llegar al mundo final donde termina el juego. Ésto lo hace muy divertido, porque puedes jugarlo una y otra vez, posiblemente descubriendo nuevos mundos cada vez.
Sin embargo, tu preocupación es que haya una secuencia de mundos que sea tan fácil de que lo detecten los jugadores, que se haga viral y ya todos puedan fácilmente decir que vencieron a tu juego. Para ello, quieres analizar cuál es dicha secuencia y mostrárselo al encargado del proyecto, para ver si lo dejan así o le suben el nivel de dificultad.
Para saber la dificultad de una ruta, cada mundo tiene un nivel de dificultad diferente que se debe multiplicar con los demás de la ruta, mientras más grande sea este número más difícil la ruta es.
Por detalles técnicos del juego, la dificultad de cada mundo es un número primo diferente, el cual también se utiliza como su identificador. Además, por diseño, el mundo inicial siempre es el 1, y el mundo final es el que tiene el identificador mayor.
En la primera línea encontrarás un número M, que determina el número de pares de mundos que están unidos en el videojuego.
En las siguientes M líneas, habrá dos enteros a y b, indicando que hay una manera de desplazarse del mundo a al b.
En una sola línea, deberás indicar los identificadores de los mundos a visitar del mundo inicial al final, de tal manera que la ruta tenga la menor dificultad posible. Imprime los identificadores separados por un espacio en el orden a visitar.
Se garantiza que exista al menos una ruta y, en caso de haber varias rutas con la misma dificultad, deberás escoger la primera lexicográficamente para evitar ambigüedades.
61 22 33 55 77 1111 13
1 2 3 5 7 11 13
53 73 51 35 137 13
1 3 5 13
1 ≤ M ≤ 106
1 ≤ a, b ≤ 106
a ≠ b
a y b son primos
| Название |
|---|


