#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
struct node{
int id,power;
};
const long long inf=1e18;
typedef unsigned long long ull;
static inline ull pack_key(int pos,int p) {
return (ull(pos)<<32)|(unsigned)p;
}
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;
cin>>a[i].second;
}
vector<int>pos(2);
for(int i=0;i<2;i++){
pos[i]=a[i].first;
}
auto check=[&](int id)->bool{
if(id>=0&&id<n){
return 1;
}
return 0;
};
vector<vector<int>>in(n);
for(int i=0;i<m;i++){
in[a[i].first].emplace_back(i);
}
map<ull,int>dp;
set<ull>vis;
auto dfs=[&](auto dfs,int id,int power)->int{
if(id==pos[1]){
return 0;
}
ull x=pack_key(id,power);
if(dp.count(x)){
return dp[x];
}
if(vis.count(x)){
return inf;
}
vis.insert(x);
int cur=inf;
if(check(id+power)){
int cur_=dfs(dfs,id+power,power);
if(cur_==inf);
else cur=min(cur,cur_+1);
}
if(check(id-power)){
int cur_=dfs(dfs,id-power,power);
if(cur_==inf);
else cur=min(cur,cur_+1);
}
for(auto x:in[id]){
if(a[x].second==power){
continue;
}
int cur_=dfs(dfs,id,a[x].second);
if(cur_==inf);
else cur=min(cur,cur_);
}
vis.erase(x);
return dp[x]=cur;
};
int x=dfs(dfs,pos[0],a[0].second);
cout<<(x>=inf?-1:x);
}
signed main(){
int t=1;
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
//cin>>t;
while(t--){
solve();
}
}
