#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
int c[N], p[N];
bool vis_sky[N];
set<pair<int, int>> vis_state;
vector<int> vec[N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> c[i] >> p[i];
vec[c[i]].push_back(p[i]);
}
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({ 0, c[0], p[0] });
vis_state.insert({ c[0], p[0] });
vis_sky[c[0]] = true;
while (!pq.empty())
{
auto [dist, pos, power] = pq.top();
pq.pop();
if (pos == c[1])
{
cout << dist;
return;
}
if (!vis_sky[pos]) {
vis_sky[pos] = true;
for (int new_p : vec[pos]) {
if (vis_state.find({ pos, new_p }) == vis_state.end()) {
vis_state.insert({ pos, new_p });
pq.push({ dist, pos, new_p });
}
}
}
for (int d : { -1, 1 })
{
int nx = pos + d * power;
if (nx >= 0 && nx < n) {
if (vis_state.find({ nx, power }) == vis_state.end()) {
vis_state.insert({ nx, power });
pq.push({ dist + 1, nx, power });
}
}
}
}
cout << -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
