#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e18;
signed main(){
int n,m; cin >> n >> m;
int ans = 0, en = 0;
vector<int> adj[n+7];
vector<int> vis(n+7, inf);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for(int i = 0; i < m; i++){
int u,v; cin >> u >> v; u++;
adj[u].push_back(v);
if(i == 0) {pq.push({0LL, u}); vis[u] = 0;}
if(i == 1) en = u;
}
for(int i = 1; i <= n; i++){
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
while(!pq.empty()){
auto [di ,nw] = pq.top(); pq.pop();
if(nw == en){
cout << vis[nw] << "\n"; exit(0);
}
if(di > vis[nw]) continue;
for(int p : adj[nw]){
int anfi = 1;
for(int i = p+nw; i <= n; i += p){
if(vis[i] > vis[nw]+anfi){
vis[i] = vis[nw]+anfi;
pq.push({vis[i], i});
}
anfi++;
}
anfi = 1;
for(int i = nw-p; i >= 1; i-= p){
if(vis[i] > vis[nw]+anfi){
vis[i] = vis[nw]+anfi;
pq.push({vis[i],i});
}
anfi++;
}
}
}
cout << "-1\n";
}
