using namespace std;
#include <iostream>
#include <bitset>
#include <queue>
#include <vector>
#define MAXN 3005
int N,M,pos[MAXN],po[MAXN];
bitset<MAXN> vis[MAXN],vis2;
queue<pair<int,pair<int,int>>> q;
vector<int> v[MAXN];
void insert(int dist,int x,int p) {
if(~p && !vis[x][p]) q.push({dist,{x,p}});
if(vis2[x]) return;
vis2[x] = true;
for(int u : v[x]) {
if(vis[x][u]) continue;
vis[x][u] = true;
q.push({dist,{x,u}});
}
return;
}
bool within(int n) {
return (n >= 0 && n < N);
}
int main() {
cin >> N >> M;
for(int i = 0;i < M;++i) {
cin >> pos[i] >> po[i];
v[pos[i]].push_back(po[i]);
}
insert(pos[0],0,-1);
while(!q.empty()) {
auto [u,v] = q.front();
auto [a,b] = v;
// cout << u << " " << a << " " << b << endl;
q.pop();
if(a == pos[1]) {
cout << u << endl;
return 0;
}
if(within(a - b)) insert(u + 1,a - b,b);
if(within(a + b)) insert(u + 1,a + b,b);
}
cout << -1 << endl;
}
