# 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 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`.

#### 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