/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 30228;
int n, m;
int b[MAXN];
int p[MAXN];
vector<int> kek[MAXN];
queue<pair<pair<int, int>, int> > q;
bitset<30001> was[30001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//read(FILENAME);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
}
for (int i = 0; i < m; i++) {
kek[b[i]].pb(p[i]);
}
if (b[1] == b[0]) {
cout << 0 << '\n';
return 0;
}
for (int i = 0; i < n; i++) {
sort(all(kek[i]));
kek[i].resize(distance(kek[i].begin(), unique(all(kek[i]))));
}
for (auto x: kek[b[0]]) {
q.push({{b[0], x}, 0});
was[b[0]][x] = true;
}
while (!q.empty()) {
auto x = q.front();
q.pop();
int pos = x.first.first;
int jump = x.first.second;
int cnt = x.second;
for (int f = pos - jump; f <= pos + jump; f += 2 * jump) {
if (f >= 0 && f < n) {
if (!was[f][jump]) {
was[f][jump] = true;
if (f == b[1]) {
cout << cnt + 1 << endl;
exit(0);
}
q.push({{f, jump}, cnt + 1});
}
for (auto y: kek[f]) {
if (!was[f][y]) {
was[f][y] = true;
q.push({{f, y}, cnt + 1});
}
}
kek[f].clear();
}
}
}
cout << -1 << endl;
return 0;
}
