#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int maxn = 30005, oo = 1e18;
int n, m, ans = oo, st, fn;
int pos[maxn], pov[maxn];
vector<int> adj[maxn];
bitset<maxn> bt[maxn];
bool mark[maxn];
void in(){
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> pos[i] >> pov[i];
adj[pos[i]].push_back(pov[i]);
}
st = pos[0], fn = pos[1];
}
struct state{
int c, b, p;
bool operator>(const state &a) const{
return c > a.c;
}
};
void djkasra(){
priority_queue<state, vector<state>, greater<state>> pq;
mark[st] = true;
for(auto u : adj[st]){
if(!bt[st][u]){
bt[st][u] = 1;
pq.push({0, st, u});
}
}
while(!pq.empty()){
state v = pq.top();
pq.pop();
if(v.b == fn){
ans = min(ans, v.c);
}
int nxt = v.b - v.p;
if(nxt >= 0){
if(!bt[nxt][v.p]){
bt[nxt][v.p] = 1;
pq.push({v.c + 1, nxt, v.p});
}
if(!mark[nxt]){
for(auto u : adj[nxt]){
if(!bt[nxt][u]){
bt[nxt][u] = 1;
pq.push({v.c + 1, nxt, u});
}
}
mark[nxt] = true;
}
}
nxt = v.b + v.p;
if(nxt < n){
if(!bt[nxt][v.p]){
bt[nxt][v.p] = 1;
pq.push({v.c + 1, nxt, v.p});
}
if(!mark[nxt]){
for(auto u : adj[nxt]){
if(!bt[nxt][u]){
bt[nxt][u] = 1;
pq.push({v.c + 1, nxt, u});
}
}
mark[nxt] = true;
}
}
}
}
void Engine(){
djkasra();
}
void out(){
if(ans == oo) {
cout << "-1\n";
return;
}
cout << ans << "\n";
}
int32_t main(){
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
in();
Engine();
out();
return 0;
}
