#include <bits/stdc++.h>
using namespace std;
const int N = 31000;
const int S = 174;
const int INF = (int)(1e9);
int dist[N][S], n, m;
vector<int> p[N];
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
int pos1, pos2;
for (int i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
x++;
p[x].push_back(y);
if (i == 1) pos1 = x;
if (i == 2) pos2 = x;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j < S; j++)
dist[i][j] = INF;
dist[pos1][0] = 0;
set<array<int, 3>> qq;
qq.insert({0, pos1, 0});
while (!qq.empty()) {
auto [d, u, v] = *qq.begin(); qq.erase(qq.begin());
vector<array<int, 3>> gg;
if (v == 0) {
for (int j : p[u])
if (j >= S) {
for (int k = u + j; k <= n; k += j)
gg.push_back({(k - u) / j, k, 0});
for (int k = u - j; k >= 1; k -= j)
gg.push_back({(u - k) / j, k, 0});
} else
gg.push_back({0, u, j});
} else {
gg.push_back({0, u, 0});
if (u - v >= 1)
gg.push_back({1, u - v, v});
if (u + v <= n)
gg.push_back({1, u + v, v});
}
for (auto [w, x, y] : gg)
if (d + w < dist[x][y]) {
qq.erase({dist[x][y], x, y});
dist[x][y] = d + w;
qq.insert({dist[x][y], x, y});
}
}
int ans = dist[pos2][0];
if (ans == INF) ans = -1;
cout << ans;
}
