// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 3e4 + 10;
set<int> st[maxn];
set<int> calced[maxn];
int dis[maxn];
bool done[maxn];
pii p[maxn];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> p[i].F >> p[i].S;
st[p[i].F].insert(p[i].S);
}
fill(dis, dis + maxn, -1);
deque< pair<pii, int> > q;
q.push_back({p[0], 0});
while(sz(q)){
int pos = q.front().F.F, p = q.front().F.S, d = q.front().S;
q.pop_front();
if(calced[pos].count(p))
continue;
calced[pos].insert(p);
if(done[pos] == 0){
dis[pos] = d;
for(int x : st[pos])
q.push_front({ {pos, x}, d });
}
done[pos] = 1;
if(pos >= p)
q.push_front({ {pos - p, p}, d + 1 });
if(pos + p < n)
q.push_front({ {pos + p, p}, d + 1 });
}
return cout << dis[p[1].F] << endl, 0;
}
