#include <bits/stdc++.h>
#include <ext/rope>
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define all(x) (x).begin(), (x).end()
#define x first
#define y second
using namespace std; using ll = long long;
using ld = long double; using pld = pair<ld, ld>;
using i128 = __int128_t; using f128 = __float128;
using pll = pair<ll, ll>; using tll = tuple<ll, ll, ll>;
ll n, m, k, t = 1; string s;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ll MINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll MAX = 30101; // SET MAX SIZE
constexpr ll MOD = 998244353;
pll a[MAX];
set <pll> num;
class _dij {
public:
class node{
public:
ll d;
node() : node(0){}
node(ll d) : d(d){}
ll num() const{ return d; }
bool operator<(const node& ot) const{ return num() < ot.num(); }
bool operator>(const node& ot) const{ return num() > ot.num(); }
bool operator==(const node& ot) const{ return num() == ot.num(); }
bool operator<=(const node& ot) const{ return num() <= ot.num(); }
node operator+(const node& ot) const{
return {d + ot.d};
}
operator ll(){ return d; }
};
node mx(){ return {INF}; }
node mn(){ return {0}; }
using ptl = pair <node, ll>;
ll n; vector <node> d;
vector <ll> pre;
vector <vector<ptl>> adj;
priority_queue <ptl, vector<ptl>, greater<ptl>> pq;
_dij(){}
_dij(ll n) { this->n = n; adj.resize(n + 1); }
void add(ll st, ll en, node c) { // 양방향
adj[st].push_back({ c,en });
adj[en].push_back({ c,st });
}
void addsol(ll st, ll en, node c) { // 단방향
adj[st].push_back({ c,en });
}
void init(ll st) {
d.clear(); pre.clear();
d.resize(n + 1, mx()); pre.resize(n + 1, -1);
pq.push({ mn(), st });
d[st] = mn();
while (!pq.empty()) {
auto [cn, cur] = pq.top(); pq.pop();
if(cn > d[cur]) continue;
for (auto& i : adj[cur]) {
auto [nn, nxt] = i;
node pl = nn + cn;
if (d[nxt] <= pl) continue;
d[nxt] = pl; pre[nxt] = cur;
pq.push({ pl, nxt });
}
}
}
node ret(ll n) { return d[n]; }
};
unordered_map <ll, ll> mp[MAX];
deque <pll> q;
vector <ll> arr[MAX];
void run(){
cin >> n >> m; _dij dij(n);
for(int i = 1;i <= m;i++){
cin >> a[i].x >> a[i].y;
if(i != 1) arr[a[i].x].push_back(a[i].y);
}
q.push_back({a[1].x, a[1].y});
mp[a[1].x][a[1].y] = 0;
while(!q.empty()){
auto[cur, cd] = q.front(); q.pop_front();
if(cur - cd >= 0){
if(!mp[cur - cd].count(cd)){
q.push_back({cur - cd, cd});
mp[cur - cd][cd] = mp[cur][cd] + 1;
}
}
if(cur + cd < n){
if(!mp[cur + cd].count(cd)){
q.push_back({cur + cd, cd});
mp[cur + cd][cd] = mp[cur][cd] + 1;
}
}
for(auto& i : arr[cur]){
if(mp[cur].count(i)) continue;
q.push_front({cur, i});
mp[cur][i] = mp[cur][cd];
}
arr[cur].clear();
}
ll result = INF;
for(auto [idx, v] : mp[a[2].x]){
result = min(result, v);
}
cout << (result == INF ? -1 : result);
}
int main() {
fastio; // cin >> t;
while(t--) run();
return 0;
}
