#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
int sq = 2 * sqrt(n);
vector<pii> a(m);
vector<int> adj[n];
for (auto &[x, y] : a) cin >> x >> y, adj[x].emplace_back(y);
priority_queue<pii> pq;
vector<int> dis(n, INT_MAX);
map<int, bool> mp[n];
pq.emplace(0, a[0].first);
dis[a[0].first] = 0;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (u == a[1].first) break;
if (dis[u] < -w) continue;
for (auto d : adj[u]) {
if (d <= sq && mp[u].count(d)) continue;
for (int i = u + d; i < n; i += d) {
if (dis[i] <= -w + (i - u) / d) continue;
dis[i] = -w + (i - u) / d;
pq.emplace(-dis[i], i);
if (d <= sq) mp[i][d] = true;
}
for (int i = u - d; i >= 0; i -= d) {
if (dis[i] <= -w + (u - i) / d) continue;
dis[i] = -w + (u - i) / d;
pq.emplace(-dis[i], i);
if (d <= sq) mp[i][d] = true;
}
}
}
if (dis[a[1].first] == INT_MAX) cout << -1;
else cout << dis[a[1].first];
}
