#include <bits/stdc++.h>
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<short,short>
#define SF(x) scanf("%Id",&x)
#define SF2(x,y) scanf("%Id%Id",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
using namespace std;
const long long INF = 1e9+1;
const long long MOD = 1e9+7;
const int MX=200015;
int sq=200;
int n,m;
bool vis[30005][280];
vector<short int> v[30005];
int f,t;
priority_queue< pair<short,pii> , vector< pair<short,pii> > , greater< pair<short,pii> > > pq;
void dijkstra(){
pq.P({0,{f,0}});
W(!pq.empty()){
short val=pq.top().F;
short ver=pq.top().S.F;
short j=pq.top().S.S;
pq.pop();
if(vis[ver][j])continue;
vis[ver][j]=1;
// cout<<ver<<" "<<j<<" "<<val<<endl;
if(ver==t){
cout<<val;
exit(0);
}
if(j==0){
for(auto i : v[ver]){
if(i<sq){
if(vis[ver][i]==0)
pq.P({val,{ver,i}});
}
else{
short o=1;
for(short j=ver-i;j>=0;j-=i){
if(vis[j][0]==0)
pq.P({o+val,{j,0}});
o++;
}
o=1;
for(short j=ver+i;j<n;j+=i){
if(vis[j][0]==0)
pq.P({o+val,{j,0}});
o++;
}
}
}
}
else{
if(ver-j>=0){
if(vis[ver-j][j]==0)
pq.P({val+1,{ver-j,j}});
if(vis[ver-j][0]==0)
pq.P({val+1,{ver-j,0}});
}
if(ver+j<n){
if(vis[ver+j][j]==0)
pq.P({val+1,{ver+j,j}});
if(vis[ver+j][0]==0)
pq.P({val+1,{ver+j,0}});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(i==0)f=x;
if(i==1)t=x;
v[x].pb(y);
}
dijkstra();
cout<<-1;
}
