#include<cstdio>
#include<vector>
#include<queue>
#define INF 0x7fffffff
#define f first
#define s second
using namespace std;
vector<int>cg[50005];
priority_queue<pair<int,int> >pq;
int dist[50005],ed[50005][2];
int n,m,a,b,cur,val,tmp;
inline bool valid(int idx) {
if(idx<0 || idx>=n) return false;
return true;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++) {
scanf("%d%d",&ed[i][0],&ed[i][1]);
cg[ed[i][0]].push_back(ed[i][1]);
}
for(i=0;i<n;i++) dist[i]=INF;
dist[ed[0][0]]=0;
pq.push({0,ed[0][0]});
while(!pq.empty()) {
val=-pq.top().first;
cur=pq.top().second;
pq.pop();
if(cur==ed[1][0])break;
if(dist[cur]!=val) continue;
for(i=0;i<cg[cur].size();i++) {
tmp=cg[cur][i];
for(j=cur+tmp;j<n;j+=tmp) {
if(dist[j]>dist[cur]+(j-cur)/tmp) {
dist[j]=dist[cur]+(j-cur)/tmp;
pq.push({-dist[j],j});
}
}
for(j=cur-tmp;j>=0;j-=tmp) {
if(dist[j]>dist[cur]+(cur-j)/tmp) {
dist[j]=dist[cur]+(cur-j)/tmp;
pq.push({-dist[j],j});
}
}
}
}
printf("%d",dist[ed[1][0]]==INF?-1:dist[ed[1][0]]);
}
