#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
const int N = 3e4+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;
bool vis[N][N];
queue<pair<int,int>>que;
vector<int>vec[N];
int n,m,vis1[N],cnt;
int bfs(int st,int end){
que.push({st-1,0});
while(!que.empty()){
int u = que.front().F%max(n,m)+1,dis = que.front().S;
int p = que.front().F/max(n,m);
if(u==end)
return dis;
que.pop();
vec[u].push_back(p);
int sz = vec[u].size();
for(int i=vis1[u]?sz-1:0;i<sz;i++){
int x = vec[u][i];
if(u-x>=1)
if(!vis[u-x][x])
que.push({u-x-1+x*max(n,m),dis+1}),vis[u-x][x] = 1,cnt++;
if(u+x<=n)
if(!vis[u+x][x])
que.push({u+x-1+x*max(n,m),dis+1}),vis[u+x][x] = 1,cnt++;
}
vec[u].pop_back();
vis1[u] = 1;
}
return -1;
}
int main(){
//freopen("out.txt","w",stdout);
//freopen("doge_5_18.in","r",stdin);
scanf("%d%d",&n,&m);
int start,end;
for(int i=1;i<=m;i++){
int p,pos;
scanf("%d%d",&pos,&p);
pos++;
vec[pos].push_back(p);
if(i==1)start = pos;
if(i==2)end = pos;
}
assert(start>=1&&start<=n&&end>=1&&end<=n);
printf("%d\n",bfs(start,end));
//printf("%d\n",cnt);
}
