// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
const int maxn = 3e4 + 10;
int n, m;
vector<pair<int, int>> adj[maxn];
vector<pair<int, int>> inp;
set<int> s[maxn];
vector<int> dijkstra(int a){
vector<int> dist(n + 1, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[a] = 0;
pq.push({0, a});
while(!pq.empty()){
int x = pq.top().se;
int d = pq.top().fi;
pq.pop();
if(d > dist[x]) continue;
for(auto &elm: adj[x]){
if(dist[elm.fi] > d + elm.se){
dist[elm.fi] = d + elm.se;
pq.push({dist[elm.fi], elm.fi});
}
}
}
return dist;
}
void solve(){
cin >> n >> m;
for(int i=0; i<m; ++i){
int x, y;cin >> x >> y;
inp.push_back({x, y});
s[inp[i].fi].insert(y);
}
int sta = inp[0].fi, en = inp[1].fi;
sort(alle(inp));
inp.erase(unique(alle(inp)), inp.end());
for(auto &elm: inp){
int cost = 0;
for(int i = elm.fi + elm.se; i < n; i += elm.se){
adj[elm.fi].push_back({i, ++cost});
if(s[i].find(elm.se) != s[i].end()) break;
}
cost = 0;
for(int i = elm.fi - elm.se; i >= 0; i -= elm.se){
adj[elm.fi].push_back({i, ++cost});
if(s[i].find(elm.se) != s[i].end()) break;
}
}
int ans = dijkstra(sta)[en];
if(ans == INF) cout << -1 << '\n';
else cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
