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 and (, ), indicating a road connecting cities and . The road from to is uphill, so the road from to is downhill.

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.