#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3e4 + 10, M = 5e6, INF = 1e9;
unordered_map<int, int> d;
vector<int> t[N];
bool vis[N];
deque<pii> q;
int sp, sb, se;
inline ll gg(ll a, ll b){
return a * N + b;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
for(int i=0; i<m; i++){
int p, b; cin >> p >> b;
t[p].pb(b);
if(i == 0)
sp = p, sb = b;
if(i == 1)
se = p;
}
q.push_back({sp, sb});
d[gg(sp, sb)] = 0;
while(!q.empty()){
int p = q.front().F, b = q.front().S;
int dis = d[gg(p, b)];
if(p == se)return cout << dis << '\n', 0;
q.pop_front();
if(!vis[p]){
for(auto l : t[p]){
if(d.count(gg(p, l)) == 0)
d[gg(p, l)] = dis, q.push_front({p, l});
}
vis[p] = true;
}
if(p + b < n){
if(d.count(gg(p + b, b)) == 0){
d[gg(p + b, b)] = dis + 1, q.push_back({p + b, b});
if(p + b == se)
return cout << dis + 1 << '\n', 0;
}
}
if(p - b >= 0){
if(d.count(gg(p - b, b)) == 0){
d[gg(p - b, b)] = dis + 1, q.push_back({p - b, b});
if(p - b == se)
return cout << dis + 1 << '\n', 0;
}
}
}
int mn = INF;
for(int i=0; i<=n; i++){
if(d.count(gg(se, i)))
mn = min(mn, d[gg(se, i)]);
}
if(d.size() > 1e6)
cout << 1/0 << endl;
if(mn < INF)
cout << mn << endl;
else cout << -1 << endl;
}
