#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back
int N,M;
int a[30010],P[30010];
int dist[30010];
bool chk[30010];
priority_queue<pp,vector<pp>,greater<pp> > Q;
mat path,doge;
int main(){
//freopen(".in","r",stdin);
scanf("%d%d",&N,&M);
path.assign(M+1,vec());
doge.assign(N,vec());
for(int i=0;i<M;i++){
scanf("%d%d",&a[i],&P[i]);
doge[a[i]].push_back(P[i]);
}
memset(dist,0x3f,sizeof(dist));
int INF=dist[0];
dist[a[0]]=0;
Q.push(pp(0,a[0]));
int v;
while(!Q.empty()){
do{
v=Q.top().second;Q.pop();
}while(!Q.empty()&&chk[v]);
chk[v]=1;
if(v==a[1])break;
for(int k=0;k<doge[v].size();k++){
int p=doge[v][k];
for(int i=0;i<N;i++){
if(abs(v-i)%p==0){
if(dist[i]>dist[v]+abs(v-i)/p){
dist[i]=dist[v]+abs(v-i)/p;
Q.push(pp(dist[i],i));
}
}
}
}
}
if(dist[a[1]]==INF){
puts("-1");
}else{
printf("%d",dist[a[1]]);
}
}
