Fastest Metro Route

In the year 2046, the entire urban rail transit network of OI City has been completed. Thanks to meticulous planning, the network consists of 2n subway lines arranged to form an n×n grid. Each subway line (vertical or horizontal) has n stations, and every station is located at the intersection of one vertical and one horizontal line.

Due to cost constraints, only m of these stations are designed for in-station transfers (marked with squares in the diagram). A train ride between adjacent stations always takes 2 minutes, and a transfer within a station takes an extra 1 minute. Serenade wants to determine the minimum time required to travel from school to home without leaving the station (i.e. waiting time is ignored).

You are given an integer n representing the grid size and an integer m followed by the coordinates of the transfer stations. Assume the stations are arranged in rows and columns with rows and columns numbered from 1 to n. The school is located at station (1, 1) and the home at station (n, n). You can travel along a subway line in any of the two possible directions (left/right for horizontal lines and up/down for vertical lines). However, if you want to change from one type of line to the other (i.e. horizontal to vertical or vice versa), you can only do so at a transfer station and it will cost 1 extra minute.

Your task is to compute the minimum travel time (in minutes) to get from station (1, 1) to station (n, n).

Note: It is guaranteed that at least one of station (1, n) or station (n, 1) is a transfer station, ensuring that a valid route exists.

inputFormat

The first line contains two integers n and m (where 1 ≤ n ≤ 300 and 1 ≤ m ≤ n*n), representing the grid size and the number of transfer stations, respectively.

Each of the next m lines contains two integers r and c (1 ≤ r, c ≤ n), representing the row and column of a station that allows transfer.

outputFormat

Output a single integer, the minimum time (in minutes) required to travel from station (1, 1) to station (n, n) without leaving the station.

sample

3 2
1 3
3 1

9