El Juego de la Etiqueta


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

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 n 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 x (x \neq 1). 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 n y x (2 \leq n \leq 2*10^5, 2 \leq x \leq n).

Cada una de las n - 1 líneas contienen dos enteros a y b (1\leq a, b \leq n) 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

There are no comments at the moment.