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.

[n,m] = input().split(" ")
n, m = int(n), int(m)

maxi = n**2 + 1
slate = ([0]*n)
slate.insert(0,maxi)
grid = [slate.copy() for i in range(n)]
grid.insert(0,([maxi]*(n+1)))

for i in range(m):
    [x, y] = input().split(" ")
    grid[int(x)][int(y)] = maxi


for i in range(1,n+1):
    for j in range(1,n+1):
        if grid[i][j] != maxi:
            valids = []
            if grid[i-1][j] != maxi:
                valids.append(grid[i-1][j])
            if grid[i][j-1] != maxi:
                valids.append(grid[i][j-1])
            if len(valids) != 0:
                grid[i][j] = min(valids) + 1
            elif [i,j] == [1,1]:
                grid[i][j] = 0
            else:
                grid[i][j] = maxi

print(grid[n][n] if grid[n][n] != maxi else -1)
