#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 3e4+5;
const int mxS = 200;
int n, m, sqT;
ll dis[mxN][mxS], dis2[mxN];
vector <ll> ID[mxN];
int main() {
cin >> n >> m;
for (auto &E : dis) for (auto &e : E) e = LLONG_MAX;
for (auto &e : dis2) e = LLONG_MAX;
pair <ll, ll> a[m];
sqT = ceil(sqrt(n));
for (int i = 0; i < m; i++) {
auto &[x, y] = a[i];
cin >> x >> y;
ID[x].emplace_back(y);
}
for (int i = 1; i <= n; i++) sort(ID[i].begin(), ID[i].end()), ID[i].resize(unique(ID[i].begin(), ID[i].end()) - ID[i].begin());
dis2[a[0].first] = 0;
priority_queue <tuple <ll, ll, ll>> q;
q.emplace(0, a[0].first, -1);
while (q.size()) {
auto [w, x, y] = q.top(); q.pop();
w = -w;
if (x == a[1].first) { cout << w << '\n'; return 0; }
if (y == -1) {
if (dis2[x] != w) continue;
for (auto &e : ID[x]) {
if (e <= sqT) { if (dis[x][e] > w) q.emplace(-(dis[x][e] = w), x, e); }
else {
for (int it = 1; x + it * e < n; it++) if (dis2[x + it * e] > w + it) q.emplace(-(dis2[x + it * e] = w + it), x + it * e, -1);
for (int it = -1; x + it * e >= 0; it--) if (dis2[x + it * e] > w + it) q.emplace(-(dis2[x + it * e] = w + it), x + it * e, -1);
}
}
} else {
if (dis[x][y] != w) continue;
if (x-y >= 0 && dis[x-y][y] > w + 1) q.emplace(-(dis[x-y][y] = w+ 1), x-y, y);
if (x+y < n && dis[x+y][y] > w + 1) q.emplace(-(dis[x+y][y] = w+ 1), x+y, y);
if (dis2[x] > w) q.emplace(-(dis2[x] = w), x, -1);
}
}
cout << -1 << '\n';
}
