#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>
using namespace std;
const int N = 3e4 + 5;
int c[N], p[N];
bool vis_sky[N];
set<int> vec[N];
bool vis_state[N][N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> c[i] >> p[i];
vec[c[i]].insert(p[i]);
}
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
pq.push({ 0, c[0], p[0] });
vis_state[c[0]][p[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[pos][new_p]) {
vis_state[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[nx][power]) {
vis_state[nx][power] = true;
pq.push({ dist + 1, nx, power });
}
}
}
}
cout << -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
