#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma unroll
#include <iostream>
#include<vector>
#include<math.h>
#include<set>
const int inf = 1e9;
const int mxn = 3e4 + 5;
using namespace std;
vector<int> g[mxn];
set<vector<int>> q; //{dist, pos, power}
vector<vector<int>> dist;
void vis(int i, int p, int c) {
if (dist[p][i] > c) {
if (dist[p][i] != inf) q.erase({ dist[p][i], i, p });
dist[p][i] = c;
q.insert({ c, i, p });
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n, m, s = -1, sq, t = -1; cin >> n >> m;
sq = 150;
for (int i = 0; i < m; ++i) {
int x, y; cin >> x >> y;
if (i == 0) s = x;
if (i == 1) t = x;
g[x].push_back(y);
}
dist.assign(sq, vector<int>(n, inf));
q.insert({ 0, s, 0 });
dist[0][s] = 0;
while (!q.empty()) {
auto f = *q.begin(); q.erase(q.begin());
if (f[1] == t) { cout << f[0]; return 0; }
if (f[2] == 0) {
for (auto x : g[f[1]]) {
if (x < sq)
vis(f[1], x, f[0]);
else {
if (f[1] >= x)
for (int i = f[1] - x, v = 1; i >= 0; i -= x, ++v)
vis(i, 0, v + f[0]);
if ((f[1] + x) < n)
for (int i = f[1] + x, v = 1; i < n; i += x, ++v)
vis(i, 0, v + f[0]);
}
}
}
else {
vis(f[1], 0, f[0]);
if (f[1] >= f[2])
vis(f[1] - f[2], f[2], f[0] + 1);
if ((f[1] + f[2]) < n)
vis(f[1] + f[2], f[2], f[0] + 1);
}
}
cout << -1;
}
