Bicycle Slopes
Emil wants to travel from city
1 to city n using his bicycle, but the roads connecting these cities pose a challenge. Each road has a slope, either going uphill or downhill. When Emil transitions from an uphill road to a downhill road or vice versa, he needs to change his bicycle gear to maintain a comfortable ride. Emil wants to know the minimum number of times he needs to change his bicycle gears during his journey from city 1 to city n.Output the minimum number of gear changes Emil needs to make in order to travel from city
1 to city n.Input
The first line contains two space-separated integers,
n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), representing the number of cities and the number of roads, respectively.The next
m lines each contain two space-separated integers Output
The program should print a single integer, representing the minimum number of gear changes Emil needs to make during his journey from city
1 to city n.Examples
Input | Output |
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