Велосипедные склоны
Эмиль намерен добраться из города
1 в город n на велосипеде. Однако дороги, соединяющие эти города, представляют определённую сложность: каждая из них идёт либо в гору, либо с горы. Если Эмиль переезжает с подъёмной дороги на спуск или наоборот, ему приходится переключать велосипедную передачу, чтобы поездка оставалась комфортной. Эмиля интересует, какое минимальное количество раз во время пути от города 1 до города n ему нужно будет переключить передачу.Выведите минимальное количество переключений передач, необходимое, чтобы доехать от города
1 до города n.Входные данные
Первая строка содержит два разделённых пробелом числа
n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), означающие количество городов и количество дорог соответственно.Каждая из следующих
m строк содержит по два разделённых пробелом числа и (, ), которые указывают, что есть дорога между городами и . Дорога из в идёт в гору, а в обратном направлении ( в ) — с горы.Выходные данные
Программа должна вывести одно число — минимальное количество переключений передач, которое понадобится Эмилю на пути от города
1 до города n.Примеры
Входные данные | Выходные данные |
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