#include<bits/stdc++.h> using namespace std; unordered_map<int, int> dis[30005]; vector<int> doge[30005]; int p[30005], l[30005]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin>>n>>m; for(int i = 0; i < m; i++){ cin>>p[i]>>l[i]; doge[p[i]].push_back(l[i]); } deque<pair<int, int>> w; dis[p[0]][l[0]] = 1; w.push_back({p[0], l[0]}); while(w.size() > 0){ int r = w.front().first, c = w.front().second, d = dis[r][c]; //cerr<<"A"<<r<<" "<<c<<" "<<d<<endl; w.pop_front(); //Go to another place if(r-c >= 0){ if(dis[r-c][c] == 0){dis[r-c][c] = d+1; w.push_back({r-c, c});}; } if(r+c < n){ if(dis[r+c][c] == 0){dis[r+c][c] = d+1; w.push_back({r+c, c});}; } //Transition to other doges for(int x : doge[r]){ if(dis[r][x] == 0){dis[r][x] = d; w.push_front({r, x});} } } int ans = 1e9; for(pair<int, int> i : dis[p[1]]) ans = min(ans, i.second-1); if(ans > n) cout<<-1; else cout<<ans; }