#include <bits/stdc++.h>
using namespace std ;
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 30004 * 175, M = 175;
vector < int > dis(N, 1e9);
vector < vector < pair < int , int >>> adj(N);
int conv(int i, int j, int n) {
return (i * M + j);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
pair < int , int > first, second;
vector < vector < int >> arr(1 + n);
set < pair < int , int >> s;
for(int i = 0 ; i < m ; i++) {
int a, b;
cin >> a >> b;
if(b < n) s.insert({a, b});
if(i == 0) {
first = {a, b};
} else if(i == 1) {
second = {a, b};
}
}
for(auto i : s) {
arr[i.first].push_back(i.second);
}
int st = first.first * M;
priority_queue < pair < int , int >> pq;
pq.push({0, st});
dis[st] = 0;
while(pq.size()) {
auto top = pq.top();
pq.pop();
top.first *= -1;
if(top.first != dis[top.second])
continue;
int i = top.second / M;
int j = top.second % M;
// cout << i << " " << j << " " << top.first << endl;
if(j == 0) {
for(auto nxt : arr[i]) {
if(nxt < M && dis[conv(i, nxt, n)] > top.first) {
dis[conv(i, nxt, n)] = top.first;
pq.push({-dis[conv(i, nxt, n)], conv(i, nxt, n)});
} else if(nxt >= M) {
for(int j = 1 ; j <= n ; j++) {
if(i + j * nxt < n && dis[conv(i + j * nxt, 0, n)] > top.first + j) {
dis[conv(i + j * nxt, 0, n)] = top.first + j;
pq.push({-dis[conv(i + j * nxt, 0, n)], conv(i + j * nxt, 0, n)});
}
if(i + j * nxt >= n) break;
}
for(int j = 1 ; j <= n ; j++) {
if(i - j * nxt >= 0 && dis[conv(i - j * nxt, 0, n)] > top.first + j) {
dis[conv(i - j * nxt, 0, n)] = top.first + j;
pq.push({-dis[conv(i - j * nxt, 0, n)], conv(i - j * nxt, 0, n)});
}
if(i - j * nxt < 0) break;
}
}
}
} else {
if(i + j < n && dis[conv(i + j, j, n)] > top.first + 1) {
dis[conv(i + j, j, n)] = top.first + 1;
pq.push({-dis[conv(i + j, j, n)], conv(i + j, j, n)});
}
if(i + j < n && dis[conv(i + j, 0, n)] > top.first + 1) {
dis[conv(i + j, 0, n)] = top.first + 1;
pq.push({-dis[conv(i + j, 0, n)], conv(i + j, 0, n)});
}
if(i - j >= 0 && dis[conv(i - j, j, n)] > top.first + 1) {
dis[conv(i - j, j, n)] = top.first + 1;
pq.push({-dis[conv(i - j, j, n)], conv(i - j, j, n)});
}
if(i - j >= 0 && dis[conv(i - j, 0, n)] > top.first + 1) {
dis[conv(i - j, 0, n)] = top.first + 1;
pq.push({-dis[conv(i - j, 0, n)], conv(i - j, 0, n)});
}
}
}
int ans = 1e9;
for(int i = 0 ; i < M ; i++) {
ans = min(ans, dis[second.first * M + i]);
}
if(ans >= 1e8) ans = -1;
cout << ans << endl;
return 0 ;
}
