#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define pii pair <int, int>
const int N = 3e4 + 5;
map <int, bool> m[N];
vector <pii> v[N];
vector <int> q[N];
int n, k, dis[N], a[N], b[N];
priority_queue <pii, vector <pii>, greater <pii>> p;
int main () {
// freopen ("input.txt", "r", stdin);
cin >> n >> k;
for (int i = 0; i < k; ++i) {
cin >> a[i] >> b[i];
if (m[a[i]].find (b[i]) == m[a[i]].end()) {
q[a[i]].pb (b[i]);
m[a[i]][b[i]] = 1;
}
}
for (int i = 0; i < n; ++i) {
for (int j : q[i]) {
int val = i + j;
int bal = 1;
while (val < n) {
v[i].pb ({val, bal});
if (m[val].find (j) != m[val].end()) {
break;
}
bal++;
val += j;
}
val = i - j;
bal = 1;
while (val >= 0) {
v[i].pb ({val, bal});
if (m[val].find (j) != m[val].end()) {
break;
}
bal++;
val -= j;
}
}
}
for (int i = 0; i < n; ++i) {
dis[i] = 1e9;
}
p.push ({0, a[0]});
dis[a[0]] = 0;
while (!p.empty()) {
int x = p.top().ss;
p.pop();
for (pii i : v[x]) {
if (dis[i.ff] > dis[x] + i.ss) {
dis[i.ff] = dis[x] + i.ss;
p.push({dis[i.ff], i.ff});
}
}
}
if (dis[a[1]] == 1e9) dis[a[1]] = -1;
cout << dis[a[1]];
}
