#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
bool ch[30010][175];
vector<int>con[30010];
typedef pair<int,int> ppair;
struct data{
int val,x,y;
char c;
bool operator<(const data&r)const{
return val>r.val;
}
}b;
queue<data>q,imsi;
int sw,n,m,root,s,pos,f=-1,r=0;
struct data2{
int x,p;
}a[30010];
int main()
{
int sw2,i,j,val,x,y,c,w=0;
scanf("%d %d",&n,&m);
root=sqrt(n);
for(i=0;i<m;i++){scanf("%d %d",&a[i].x,&a[i].p); con[a[i].x].push_back(a[i].p);}
b.val=0, b.x=a[0].x, b.y=a[0].p, q.push(b);
while(q.size()){
sw2=0;
while(q.size()){
x=q.front().x; val=q.front().val; y=q.front().y; c=q.front().c;
if(q.front().y<=root){
if(ch[q.front().x][q.front().y]){
q.pop();
if(q.size()==0){
while(imsi.size()){q.push(imsi.front()); imsi.pop();}
}
continue;
}
else{sw2=1; break;}
}
if(x==a[1].x){printf("%d",val); return 0;}
if(ch[x][0]==0){
for(i=0;i<con[x].size();i++){
b.val=val; b.x=x; b.y=con[x][i]; b.c=0;
q.push(b);
}
}
if(c==1 || c==0){
for(i=x+y;i<n;i+=y){
b.val=val+1; b.x=i; b.y=y; b.c=1; imsi.push(b); break;
}
}
if(c==2 || c==0){
for(i=x-y;i>=0;i-=y){
b.val=val+1; b.x=i; b.y=y; b.c=2; imsi.push(b); break;
}
}
ch[x][0]=1; q.pop();
if(q.size()==0){
while(imsi.size()){q.push(imsi.front()); imsi.pop();}
}
}
if(!sw2){sw=1; break;}
val=q.front().val; x=q.front().x; y=q.front().y; ch[x][y]=1;
if(x==a[1].x) break;
if(ch[x][0]==0){
for(i=0;i<con[x].size();i++){
b.val=val; b.x=x; b.y=con[x][i]; b.c=0;
q.push(b);
}
}
ch[x][0]=1;
q.pop();
if(x+y<n) b.val=val+1, b.x=x+y, b.y=y, b.c=0, imsi.push(b);
if(x-y>=0) b.val=val+1, b.x=x-y, b.y=y, b.c=0, imsi.push(b);
if(q.size()==0){
while(imsi.size()){q.push(imsi.front()); imsi.pop();}
}
}
if(sw) printf("-1");
else printf("%d",val);
return 0;
}
