Pendientes para bicicletas
Emil desea viajar desde la ciudad
1 hasta la ciudad n en bicicleta, pero las carreteras que enlazan estas ciudades representan un desafío. Cada carretera cuenta con una inclinación: puede ser de subida o de bajada. Cuando Emil pasa de una carretera de subida a otra de bajada, o viceversa, necesita cambiar la marcha de su bicicleta para mantener un recorrido cómodo. Emil quiere saber cuántas veces, como mínimo, deberá cambiar de marcha durante el trayecto que va de la ciudad 1 a la ciudad n.Muestra la cantidad mínima de cambios de marcha que Emil necesita realizar para completar el viaje desde la ciudad
1 hasta la ciudad n.Entrada
La primera línea contiene dos enteros separados por espacio,
n y m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), que representan la cantidad de ciudades y la cantidad de carreteras, respectivamente.Las siguientes
m líneas contienen, cada una, dos enteros separados por espacio y (, ), que describen una carretera que conecta las ciudades y . La carretera de a es de subida, por lo que la carretera de a será de bajada.Salida
El programa debe imprimir un único número entero que represente la cantidad mínima de cambios de marcha que Emil debe realizar durante su viaje de la ciudad
1 a la ciudad n.Ejemplos
Entrada | Salida |
5 5
1 2
2 3
5 3
4 2
4 5 | 1 |
3 3
1 2
2 3
3 1 | 0 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB