#include <bits/stdc++.h>
using namespace std;
struct edge{
int v, c;
};
const int maxpow = 2000;
int n,m,k,x,y,z;
int pos[4002005], power[4002005];
vector<edge> gph[4002005];
int dis[4002005], inq[4002005];
deque<int> nxt;
int f(int i, int j) { //2d to 1d
return (i-1)*maxpow+j;
}
void spfa() {
for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9;
dis[f(pos[1],power[1])] = 0;
nxt.push_back(f(pos[1],power[1]));
inq[f(pos[1],power[1])] = 1;
while (nxt.size()) {
auto tmp = nxt.front();
nxt.pop_front();
inq[tmp] = 0;
for (auto i : gph[tmp]) {
if (dis[tmp] + i.c < dis[i.v]) {
dis[i.v] = dis[tmp] + i.c;
if (!inq[i.v]) nxt.push_back(i.v);
inq[i.v] = 1;
}
}
}
if (dis[n*maxpow+pos[2]] == 1e9) cout << "-1\n";
else cout << dis[n*maxpow+pos[2]] << '\n';
}
int main() {
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> pos[i] >> power[i];
for (int i = 1; i <= m; i++) pos[i]++;
for (int i = 1; i <= maxpow; i++) { //pow
for (int j = 1; j <= i; j++) {
for (int l = j; l+i <= n; l += i) { //pos
gph[f(l,i)].push_back({f(l+i,i),1});
gph[f(l+i,i)].push_back({f(l,i),1});
}
}
for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*maxpow+j,0});
}
for (int i = 1; i <= m; i++) gph[n*maxpow+pos[i]].push_back({f(pos[i],power[i]),0});
spfa();
}
