#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int SQ = 1500;
const int MN = 30030;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(ii x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(splitmix64(x.first+FIXED_RANDOM)+x.second+FIXED_RANDOM);
}
};
unordered_map<ii,int, chash> dist;
ii ok[MN];
vi go[MN];
bitset<MN> vs;
int dx[2] = {-1,1};
int had[MN][SQ];
int ged(int u, int p) {
if(p < SQ) {return had[u][p];}
if(dist.count({u,p})) {
return dist[{u,p}];
}
return -1;
}
void sed(int u, int p, int val) {
if(p < SQ) {
had[u][p] = val;
return;}
dist[{u,p}] = val;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n,m;
cin >> n >> m;
memset(had,-1,sizeof(had));
for(int i=0;i<m;i++) {
int a,p;
cin >> a >> p;
ok[i] = {a,p};
go[a].push_back(p);
}
deque<ii> q;
int sr = ok[0].first;
vs.set(sr);
for(int i=0;i<go[sr].size();i++) {
if(ged(sr,go[sr][i]) == -1) {
q.push_front({sr,go[sr][i]});
sed(sr,go[sr][i],0);
}
}
int res = -1;
int fin = ok[1].first;
while(!q.empty()) {
ii co = q.front();q.pop_front();
int u = co.first;
int p = co.second;
int di = ged(u,p);
//cout << "look " << u << " " << p << " = " << di << '\n';
if(u == fin) {
res = di;break;
}
if(!vs[u]) {
vs.set(u);
//cout << "unlock " << u << '\n';
for(int i=0;i<go[u].size();i++) {
if(ged(u,go[u][i]) == -1) {
q.push_front({u,go[u][i]});
sed(u,go[u][i],di);
}
}
q.push_front(co);
continue;
}
for(int i=0;i<2;i++) {
int v = u+dx[i]*p;
if(v < 0 || v >= n) {continue;}
if(ged(v,p) != -1) {continue;}
sed(v,p,di+1);
q.push_back({v,p});
}
}
cout << res << '\n';
}
