#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// PUT IT BEFORE THE INCLUDE
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int M = 3e4 + 7;
struct cmp{
bool operator()(array < int , 3 > const& a , array < int , 3 > const& b){
return b[0] < a[0];
}
};
void solve(){
int n, m;
cin >> n >> m;
pair < int , int > doge[m];
vector < int > root[M];
for(int i = 0;i<m;i++){
cin >> doge[i].first >> doge[i].second;
root[doge[i].first].push_back(doge[i].second);
}
set < pair < int , int > > vis;//konum zıplayış
priority_queue < array < int , 3 > , vector < array < int , 3 > > , cmp > pq;//dist , konum , zıplayış
pq.push({0,doge[0].first,0});
while(pq.size()){
array < int , 3 > tmp = pq.top();
pq.pop();
if(vis.count({tmp[1],tmp[2]})){
continue;
}
if(tmp[1] == doge[1].first){
cout << tmp[0] << endl;
return;
}
vis.insert({tmp[1],tmp[2]});
if(tmp[1] + tmp[2] < n)pq.push({tmp[0] + 1 , tmp[1] + tmp[2] , tmp[2]});
if(tmp[1] - tmp[2] >= 0)pq.push({tmp[0] + 1 , tmp[1] - tmp[2] , tmp[2]});
for(auto itr : root[tmp[1]]){
if(tmp[1] + itr < n)pq.push({tmp[0] + 1 , tmp[1] + itr , itr});
if(tmp[1] - itr >= 0)pq.push({tmp[0] + 1 , tmp[1] - itr , itr});
}
}
cout << -1 << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
