#include<bits/stdc++.h>
using namespace std;
const int nax = 3e4 + 3;
const int INF = 1e9;
const long long pr = 1e9 + 9;
const int cax = 1e6 + 3;
int b[nax], p[nax];
vector<int>doges[nax];
vector<pair<long long,int>>dist[cax];
int get(int x, int y) {
long long H = x * pr + y;
int H2 = H % cax;
for(auto x : dist[H2]) {
if(x.first==H) return x.second;
}
return INF;
}
void put(int x, int y, int val) {
long long H = x * pr + y;
int H2 = H % cax;
dist[H2].emplace_back(H, val);
assert(dist[H2].size()<=5);
}
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=0; i<m; ++i) {
cin>>b[i]>>p[i];
doges[b[i]].push_back(p[i]);
}
put(b[0], 0, 0);
deque<tuple<int,int,int>>dq;
dq.push_back({b[0], 0, 0});
while(!dq.empty()) {
auto x = dq.front();
dq.pop_front();
int ss, j, d;
tie(ss, j, d) = x;
if(d!=get(ss, j)) continue;
if(ss==b[1]) {
cout<<d<<'\n';
return;
}
if(j==0) {
for(int z : doges[ss]) {
if(get(ss, z)>d) {
put(ss, z, d);
dq.emplace_front(ss, z, d);
}
}
} else {
if(ss+j<n) {
if(get(ss+j, j)>d+1) {
put(ss+j, j, d+1);
dq.emplace_back(ss+j, j, d+1);
}
if(get(ss+j, 0)>d+1) {
put(ss+j, 0, d+1);
dq.emplace_back(ss+j, 0, d+1);
}
}
if(ss-j>=0) {
if(get(ss-j, j)>d+1) {
put(ss-j, j, d+1);
dq.emplace_back(ss-j, j, d+1);
}
if(get(ss-j, 0)>d+1) {
put(ss-j, 0, d+1);
dq.emplace_back(ss-j, 0, d+1);
}
}
}
}
cout<<"-1\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
