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 solut (x,y):
    global k,mini
    if x==n and y==n:
        if mini>k: mini=k
    for x1,y1 in [(x+1,y),(x,y+1)]:
        if not((x1,y1) in col) and not((x1,y1) in w) and x1<=n and y1<=n:
            st.append((x1,y1),)
            col.add((x1,y1),)
            k+=1
            solut(x1,y1);
            k-=1
            col.discard((x1,y1))
            st.pop()
w=set()
n,m = map(int,input().split())
for i in range(m):
    w.add(tuple(map(int,input().split())))
st=[(1,1),]
col = set(); col.add((1,1),)
k=0;mini=100000
while st:
    x,y=st.pop()    
    solut(x,y)
print(mini)
