Iahub got lost in a very big desert. The desert can be represented as a *n* × *n* square matrix, where each cell is a zone of the desert. The cell (*i*, *j*) represents the cell at row *i* and column *j* (1 ≤ *i*, *j* ≤ *n*). Iahub can go from one cell (*i*, *j*) only down or right, that is to cells (*i* + 1, *j*) or (*i*, *j* + 1). 

Also, there are *m* cells that are occupied by volcanoes, which Iahub cannot enter. 

Iahub is initially at cell (1, 1) and he needs to travel to cell (*n*, *n*). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (*n*, *n*).
The first line contains two integers *n* (1 ≤ *n* ≤ 10<sup class="upper-index">9</sup>) and *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). Each of the next *m* lines contains a pair of integers, *x* and *y* (1 ≤ *x*, *y* ≤ *n*), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to *n* from top to bottom, and matrix columns are numbered from 1 to *n* from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location.
import sys
read_ints = lambda : map(int, sys.stdin.readline().split())
n, m = read_ints()
v = [(read_ints()) for i in range(m)]

e = n*2-2

l = [(1, 1, 0)]
while(len(l) > 0):
    (x, y, z) = l[0]
    if (x, y, z) is (n, n, e):
        print(z)
        break
    if x > n or y > n or (x, y) in v: return
    l.append((x+1, y, z+1))
    l.append((x, y+1, z+1))