#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for(int i=0; i<M; i++) cin >> B[i] >> P[i];
// 1) Collect unique powers <=√N and >√N separately:
int S = sqrt(N);
vector<vector<int>> powers(N);
for(int i=0;i<M;i++){
powers[ B[i] ].push_back(P[i]);
}
// 2) Assign IDs:
// - pos nodes: [0..N-1]
// - state nodes: subsequent
int V = N;
vector<unordered_map<int,int>> id_state(N);
for(int b=0;b<N;b++){
sort(powers[b].begin(), powers[b].end());
powers[b].erase(unique(powers[b].begin(), powers[b].end()), powers[b].end());
for(int p: powers[b]){
id_state[b][p] = V++;
}
}
// 3) Build graph
vector<vector<pair<int,int>>> adj(V);
auto addEdge = [&](int u,int v,int w){
adj[u].emplace_back(v,w);
};
for(int b=0;b<N;b++){
for(int p: powers[b]){
int u = id_state[b][p];
// jump left/right
int nb = b + p;
if(nb<N) addEdge(u, id_state[nb][p], 1);
nb = b - p;
if(nb>=0) addEdge(u, id_state[nb][p], 1);
// to dummy(b)
addEdge(u, b, 1);
}
// from dummy(b) to each (b,p)
for(int p: powers[b]){
addEdge(b, id_state[b][p], 0);
}
}
// 4) Dijkstra
vector<ll> dist(V, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
int start = id_state[B[0]][P[0]];
int target = id_state[B[1]][P[1]];
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(d > dist[u]) continue;
for(auto &e: adj[u]){
int v = e.first, w = e.second;
if(dist[v] > d + w){
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
ll ans = dist[target];
cout << (ans==INF? -1 : ans) << "\n";
return 0;
}
