#include<bits/stdc++.h> using namespace std; bitset<30000> f[30000]; 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<pair<int, int>, int>> w; w.push_back({{p[0], l[0]}, 0}); f[p[0]][l[0]] = 1; int ans = 1e9; while(w.size() > 0){ int r = w.front().first.first, c = w.front().first.second, d = w.front().second; //cerr<<"A"<<r<<" "<<c<<" "<<d<<endl; w.pop_front(); if(r == p[1]) ans = min(ans, d); //Go to another place if(r-c >= 0 && f[r-c][c] == 0){ f[r-c][c] = 1; w.push_back({{r-c, c}, d+1}); } if(r+c < n && f[r+c][c] == 0){ f[r+c][c] = 1; w.push_back({{r+c, c}, d+1}); } //Transition to other doges for(int x : doge[r]) if(f[r][x] == 0){ f[r][x] = 1; w.push_front({{r, x}, d}); } } if(ans >= 1e9) cout<<-1; else cout<<ans; }