#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const long long inf=1e18;
typedef unsigned long long ull;
struct pair_hash{
static ull splitmix64(ull x){
x+=0x9e3779b97f4a7c15;
x=(x^(x>>30))*0xbf58476d1ce4e5b9;
x=(x^(x>>27))*0x94d049bb133111eb;
return x^(x>>31);
}
size_t operator()(const pair<int,int>&p)const{
static const ull r=chrono::steady_clock::now().time_since_epoch().count();
ull k=(ull(p.first)<<32)|unsigned(p.second);
return splitmix64(k+r);
}
};
void solve(){
int n,m;
cin>>n>>m;
vector<pair<int,int>>a(m);
for(int i=0;i<m;i++){
cin>>a[i].first>>a[i].second;
}
vector<vector<int>>in(n);
for(int i=0;i<m;i++){
in[a[i].first].push_back(i);
}
vector<int>pos(2);
pos[0]=a[0].first;pos[1]=a[1].first;
unordered_map<pair<int,int>,int,pair_hash>dp;
unordered_set<pair<int,int>,pair_hash>vis;
dp.reserve(n*2);vis.reserve(n*2);
auto dfs=[&](auto self,int id,int power)->int{
if(id==pos[1])return 0;
auto key=make_pair(id,power);
if(dp.count(key))return dp[key];
if(vis.count(key))return inf;
vis.insert(key);
int best=inf;
if(id+power>=0&&id+power<n){
int r=self(self,id+power,power);
if(r<inf)best=min(best,r+1);
}
if(id-power>=0&&id-power<n){
int r=self(self,id-power,power);
if(r<inf)best=min(best,r+1);
}
for(int idx:in[id]){
int np=a[idx].second;
if(np==power)continue;
int r=self(self,id,np);
if(r<inf)best=min(best,r);
}
vis.erase(key);
return dp[key]=best;
};
int ans=dfs(dfs,pos[0],a[0].second);
cout<<(ans>=inf?-1:ans)<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
while(t--)solve();
return 0;
}
