Pendenze in Bicicletta
Emil vuole viaggiare dalla città
1 alla città n in bicicletta, ma le strade che collegano queste città gli creano qualche difficoltà. Ogni strada ha una pendenza, in salita o in discesa. Quando Emil passa da una strada in salita a una in discesa o viceversa, deve cambiare la marcia della sua bicicletta per mantenere un’andatura confortevole. Emil desidera sapere il numero minimo di volte in cui dovrà cambiare marcia durante il viaggio dalla città 1 alla città n.Stampa il numero minimo di cambi di marcia necessari perché Emil possa andare dalla città
1 alla città n.Dati in ingresso
La prima riga contiene due interi separati da spazio,
n e m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), che rappresentano rispettivamente il numero di città e il numero di strade.Le successive
m righe contengono ciascuna due interi e (1 ≤ ai, bi ≤ n, ai ≠ bi), che indicano una strada tra le città e . La strada da a è in salita, mentre quella da a è in discesa.Dati in uscita
Il programma deve stampare un solo intero, che rappresenti il numero minimo di cambi di marcia che Emil dovrà effettuare durante il suo viaggio dalla città
1 alla città n.Esempi
Dati in ingresso | Dati in uscita |
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