#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int n, m, b[N], p[N];
vector<int> at[N];
map<pair<int, int>, int> dist;
bool vis[N];
void f(int v){
queue<pair<int, int>> q;
for (int x : at[v]){
q.push({v, x});
dist[{v, x}] = 0;
}
vis[v] = 1;
while (!q.empty()){
auto [v, x] = q.front();
q.pop();
for (int u : {v + x, v - x}){
if (u < 0 or u >= n) continue;
if (dist.find({u, x}) == dist.end())
dist[{u, x}] = 1e9;
if (dist[{u, x}] > dist[{v, x}] + 1){
dist[{u, x}] = dist[{v, x}] + 1;
q.push({u, x});
if (!vis[u]){
vis[u] = 1;
for (int y : at[u]){
q.push({u, y});
dist[{u, y}] = dist[{u, x}];
}
}
}
}
}
}
int main(){
cin >> n >> m;
for (int i = 0; i < m; i ++){
cin >> b[i] >> p[i], at[b[i]].push_back(p[i]);
}
f(b[0]);
int ans = 1e9;
for (auto [P, d] : dist)
if (P.first == b[1] and ans > d)
ans = d;
if (ans == 1e9) ans = -1;
cout << ans << endl;
}
