El Juego de la Etiqueta
Nuestros siempre competitivos amigos, Alice y Bob, están jugando el juego de la etiqueta pero se han aburrido, por lo que Alice ofrece una modificación. Ahora el juego debe ser jugado en un árbol de vértices, no dirigido y cuya raíz es el vértice 1.
Alice comienza en el vértice 1 y Bob en un vértice . Los movimientos se harán por turnos y Bob empieza. En un movimiento uno puede elegir quedarse en el vértice en que se encuentra o moverse a un vértice vecino.
El juego finaliza cuando Alice se mueve al mismo vértice donde se encuentra situado Bob. Alice quiere minimizar el número total de movimientos y Bob quiere maximizarlo.
Tu debes escribir un programa el cual determine cuantos movimientos durará el juego. Recuerda que ambos jugadores juegan óptimamente.
Entrada
La primera linea contiene dos números y .
Cada una de las líneas contienen dos enteros y las aristas del ábol. Se garantiza que las aristas forman un árbol válido.
Salida
Imprima el número total de movimientos que Alice y Bob harán.
Ejemplo #1 de Entrada
4 3
1 2
2 3
2 4
Ejemplo #1 de Salida
4
Ejemplo #2 de Entrada
5 2
1 2
2 3
3 4
2 5
Ejemplo #2 de Salida
6
Explicación
La lista de movimientos realizados por Alice y Bob para el caso uno son:
B: se queda en el vértice 3
A: va para el vértice 2
B: se queda en el vértice 3
A: va para el vértice 3
Y para el segundo caso de prueba:
B: va para el vértice 3
A: va para el vértice 2
B: va para el vértice 4
A: va para el vértice 3
B: se queda en el vértice 4
A: va para el vértice 4
Comments