Declives de Bicicleta
Emil quer viajar da cidade
1 até à cidade n usando a sua bicicleta, mas as estradas que ligam estas cidades representam um desafio. Cada estrada tem uma inclinação, podendo ser a subir ou a descer. Sempre que Emil passa de uma estrada a subir para outra a descer (ou vice-versa), ele precisa de mudar a mudança da bicicleta para manter o conforto. O objetivo de Emil é descobrir o número mínimo de vezes que terá de mudar de mudanças ao longo do percurso desde a cidade 1 até à cidade n.Apresente o número mínimo de mudanças de marcha necessárias para que Emil consiga viajar da cidade
1 até à cidade n.Entrada
A primeira linha contém dois inteiros separados por espaço,
n e m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), que indicam, respetivamente, o número de cidades e o número de estradas.As seguintes
m linhas contêm, cada uma, dois inteiros e separados por espaço (, ), representando uma estrada que liga as cidades e . A estrada de para é a subir, logo a estrada de para é a descer.Saída
O programa deve imprimir um único inteiro que representa o número mínimo de mudanças de marcha que Emil precisa de fazer para completar a viagem entre a cidade
1 e a cidade n.Exemplos
Entrada | Saída |
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