#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define F first
#define S second
#define var auto
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Max = 30002;
const int Sq = 200;
const int SQ = 2*Sq+1;
const int INF = 1000000010;
vector<int> pws[Max];
vector<int> t2[Max];
vector<int> t1[Max];
int dist[Max * SQ];
int n , m;
#define index(a , b) ((a)*SQ + (b))
void Find(int v)
{
deque<int> q;q.pb(v);dist[v] = 0;
while(q.size())
{
v = q.front();
q.pop_front();
int x = v / SQ;
int y = v - x * SQ;
//if(y <= Sq)
// cout << "(" << x << "," << y << ") = " << dist[v] << "\n";
if(y == 0)
{
//yal haye 0
for(int z : t1[x])
{
if(dist[index(x , z)] > dist[v])
{
dist[index(x , z)] = dist[v];
q.push_front(index(x , z));
}
}
//yal haye 1
if(dist[index(x , Sq+1)] > dist[v] + 1)
{
dist[index(x , Sq+1)] = dist[v] + 1;
q.pb(index(x , Sq+1));
}
}
else if(y <= Sq)
{
//yal haye 0
if(dist[index(x , 0)] > dist[v])
{
dist[index(x , 0)] = dist[v];
q.push_front(index(x , 0));
}
//yal haye 1
if(x + y < n)
if(dist[index(x + y , y)] > dist[v] + 1)
{
dist[index(x + y , y)] = dist[v] + 1;
q.pb(index(x + y , y));
}
if(x - y >= 0)
if(dist[index(x - y , y)] > dist[v] + 1)
{
dist[index(x - y , y)] = dist[v] + 1;
q.pb(index(x - y , y));
}
}
else
{
y -= Sq;
//yal haye 0
for(int z : t2[x])
{
if(x + y * z >= n)
break;
if(dist[index(x + y * z, 0)] > dist[v])
{
dist[index(x + y * z , 0)] = dist[v];
q.push_front(index(x + y * z , 0));
}
}
for(int z : t2[x])
{
if(x - y * z < 0)
break;
if(dist[index(x - y * z, 0)] > dist[v])
{
dist[index(x - y * z , 0)] = dist[v];
q.push_front(index(x - y * z , 0));
}
}
//yal haye 1
if(y != Sq)
if(dist[v + 1] > dist[v] + 1)
{
dist[v + 1] = dist[v] + 1;
q.pb(v + 1);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
int b0 = -1;
int b1 = -1;
for(int i = 0; i < m ; i++)
{
int b , p;cin >> b >> p;
pws[b].pb(p);
if(i == 0)
b0 = b;
if(i == 1)
b1 = b;
}
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < SQ; j++)
dist[index(i , j)] = INF;
sort(pws[i].begin() , pws[i].end());
pws[i].resize(unique(pws[i].begin() , pws[i].end()) - pws[i].begin());
for(int x : pws[i])
{
if(x <= Sq)
t1[i].pb(x);
else
t2[i].pb(x);
}
}
Find(index(b0 , 0));
if(dist[index(b1 , 0)] < INF)
cout << dist[index(b1 , 0)] << '\n';
else
cout << -1 << '\n';
}
