#include <bits/stdc++.h>
using namespace std;
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
const int N = 3e4 + 10;
int n, m, b[N], p[N], ans = 1e9;
vector<int> at[N];
unordered_map<long long, int, custom_hash> dist;
bool vis[N];
void f(int v, int e){
queue<pair<int, int>> q;
for (int x : at[v]){
q.push({v, x});
dist[v * N + x] = 0;
}
vis[v] = 1;
while (!q.empty()){
auto [v, x] = q.front();
q.pop();
if (v == e){
ans = dist[v * N + x];
break;
}
for (int u : {v + x, v - x}){
if (u < 0 or u >= n) continue;
if (dist.find(u * N + x) == dist.end())
dist[u * N + x] = 1e9;
if (dist[u * N + x] > dist[v * N + x] + 1){
dist[u * N + x] = dist[v * N + x] + 1;
q.push({u, x});
if (!vis[u]){
vis[u] = 1;
for (int y : at[u]){
if (dist.find(u * N + y) != dist.end())
continue;
q.push({u, y});
dist[u * N + y] = dist[u * N + 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], b[1]);
if (ans == 1e9) ans = -1;
cout << ans << endl;
}
