Caminata Hamiltooniana
A Alice le encanta caminar a través de senderos. A menudo viaja por bosques y montañas durante varios días, llevando sólo una mochila.
Para el próximo verano, ha decidido viajar a una hermosa zona en la que hay un gran número de cabañas: lugares en los que los excursionistas pueden depositar un saco de dormir y pasar la noche.
Estas cabañas están conectadas por senderos de rutas, caminos a lo largo del paisaje de la zona que llevan a la siguiente cabaña.
El plan de Alice es realizar una excursión de varios días. Cada día, caminará por los senderos hasta una nueva cabaña para pasar la noche.
Ella puede recorrer hasta tres senderos en un día, ya que recorrer cuatro es demasiado agotador. Para poder conocer todas las cabañas posibles, Alice ha decidido que quiere dormir en todas ellas al menos una vez. Sin embargo, el verano tiene un número limitado de días: no tiene tiempo para visitar una cabaña varias veces.
Alice se ha dado cuenta de que esto requiere una planificación cuidadosa de su caminata y se pregunta cómo encontrar esa ruta. Determina a qué cabaña debe ir Alice cada día. La figura muestra una posible ruta para el segundo caso de ejemplo.
Entrada
La entrada consiste en:
- Una línea que contiene dos enteros
y
, el número de cabañas y senderos de rutas.
líneas que contienen cada una dos enteros
,
\((1 \le x, y \le n, x ≠ y)\), que indican que hay un sendero de ruta entre las cabañas
Salida
Salir el orden en que Alice debe visitar las n cabañas. No es necesario minimizar el número total de rutas de senderismo. Si hay varias soluciones válidas, puede dar salida a cualquiera de ellas.
Ejemplo de Entrada #1
4 3
1 2
1 3
1 4Ejemplo de Salida #1
2 1 3 4
Figura: La entrada y una ruta posible (flechas rojas discontinuas) para el segundo caso de muestra.
Ejemplo de Entrada #2
7 8
1 2
1 7
2 3
2 4
3 4
4 5
5 6
5 7Ejemplo de Salida #2
1 4 2 5 7 6 3
Comments
todavia no ando muy metido en grafos asi que puede que este mal, pero este problema no saldria con un dfs?
easy