#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;
//int dis[30100];
vector<int>e[30100];
set<int>st[30100];
map<pair<int,int>,int>vis;
map<pair<int,int>,int>dis;
int ar[30100];
int br[30100];
int frm[30100];
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>ar[i]>>br[i];
st[ar[i]].insert(br[i]);
// e[ar[i]].push_back(br[i]);
}
for(int i=0;i<n;i++){
for(auto it=st[i].begin();it!=st[i].end();it++){
e[i].push_back(*it);
}
e[i].push_back(0);
}
dis[{ar[0],0}]=1;
deque<pair<int,int>>dq;
dq.push_back({ar[0],0});
while(dq.size()){
int nw=dq.front().first;
int nwd=dq.front().second;
dq.pop_front();
if(vis[{nw,nwd}]){continue;}
vis[{nw,nwd}]=1;
for(int i=0;i<e[nw].size();i++){
int d=e[nw][i];
if(vis[{nw,d}]){continue;}
if(dis[{nw,d}]==0){
dis[{nw,d}]=dis[{nw,nwd}];
dq.push_front({nw,d});
continue;
}
if(dis[{nw,d}]>dis[{nw,nwd}]){
dis[{nw,d}]=dis[{nw,nwd}];
dq.push_front({nw,d});
}
}
if(nw+nwd<n){
if(dis[{nw+nwd,nwd}]==0){
dis[{nw+nwd,nwd}]=dis[{nw,nwd}]+1;
dq.push_back({nw+nwd,nwd});
//continue;
}
if(dis[{nw+nwd,nwd}]>dis[{nw,nwd}]+1){
dis[{nw+nwd,nwd}]=dis[{nw,nwd}]+1;
dq.push_back({nw+nwd,nwd});
}
}
if(nw-nwd>=0){
if(dis[{nw-nwd,nwd}]==0){
dis[{nw-nwd,nwd}]=dis[{nw,nwd}]+1;
dq.push_back({nw-nwd,nwd});
// continue;
}
if(dis[{nw-nwd,nwd}]>dis[{nw,nwd}]+1){
dis[{nw-nwd,nwd}]=dis[{nw,nwd}]+1;
dq.push_back({nw-nwd,nwd});
}
}
}
cout<<dis[{ar[1],0}]-1;
}
