#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5, SQ = 175;
int n, m, b[N], p[N], dist[N][SQ];
vector<int> v[N];
deque<tuple<int, int, int>> q;
unordered_map<int, int> dis[N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1;i<=m;i++){
cin >> b[i] >> p[i];
v[b[i]].push_back(p[i]);
}
memset(dist, -1, sizeof dist);
dist[b[1]][p[1]] = 0;
q.push_front({0, b[1], p[1]});
while(!q.empty()){
auto [d, u, p] = q.front();
q.pop_front();
for(auto x : v[u]){
if(x > SQ){
if(!dis[u].count(x)){
dis[u][x] = d;
q.push_front({d, u, x});
}
}else if(dist[u][x] == -1){
dist[u][x] = d;
q.push_front({d, u, x});
}
}
if(p > SQ){
if(u - p >= 0 && !dis[u - p].count(p)){
dis[u - p][p] = d + 1;
q.push_back({d + 1, u - p, p});
}
if(u + p < n && !dis[u + p].count(p)){
dis[u + p][p] = d + 1;
q.push_back({d + 1, u + p, p});
}
}else{
if(u - p >= 0 && dist[u - p][p] == -1){
dist[u - p][p] = d + 1;
q.push_back({d + 1, u - p, p});
}
if(u + p < n && dist[u + p][p] == -1){
dist[u + p][p] = d + 1;
q.push_back({d + 1, u + p, p});
}
}
}
if(p[2] > SQ){
if(dis[b[2]].count(p[2])) cout << dis[b[2]][p[2]];
else cout << -1;
}else{
cout << dist[b[2]][p[2]];
}
}
