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.
def aq(x,y):
    global n
    if x==y==n:
        print(2*(n-1))
        exit(0)
    if x<n and not(a[x+1][y]):
        a[x+1][y]=True
        aq(x+1,y)
    if y<n and not(a[x][y+1]):
        a[x][y+1]=True
        aq(x,y+1)
n,m=map(int,input().split())
t=False
a=[[False]*(n+1) for i in range(n+1)]
for i in range(m):
    x,y=map(int,input().split())
    a[x][y]=True
aq(1,1)
print(-1)