#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 2000, m0 = 30000;
int n, m, can[n0][n0], ans[n0], inf;
vector <int> d[n0];
vector <array <int, 2>> g[n0];
void dijsktra(int x) {
priority_queue <array <int, 2>, vector <array <int, 2>>, greater <array <int, 2>>> q;
memset(& ans, 0x3f, sizeof(ans));
inf = ans[0];
ans[x] = 0;
q.push({ans[x], x});
while (!q.empty()) {
auto V = q.top();
q.pop();
int v = V[1];
if (ans[v] < V[0]) continue;
for (auto & i : g[v]) {
int to = i[0], w = i[1];
if (ans[to] > ans[v] + w) {
ans[to] = ans[v] + w;
q.push({ans[to], to});
}
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> m;
int A = -1, B = -1;
for (int i = 0; i < m; i++) {
int x, p;
cin >> x >> p;
if (i == 0) A = x;
if (i == 1) B = x;
can[x][p] = 1;
}
for (int i = 0; i < n; i++)
for (int j = i - 1; j >= 1; j--)
if (i % j == 0) d[i].pb(j);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int dist = abs(i - j), res = -1;
for (int k : d[dist]) {
if (can[i][k]) {
res = dist / k;
break;
}
}
if (res == -1) continue;
g[i].pb({j, res});
}
}
dijsktra(A);
if (ans[B] == inf) ans[B] = -1;
cout << ans[B];
}
