#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
using namespace std;
#define pi pair<int , int>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 3e4 + 5;
const long long mod = 1e9 + 7;
const int SQ = 176;
typedef long long ll;
int l,r,mid;
int n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
//cout << mid <<" " << mid*mid-mid <<endl;
if (((mid-1)*mid)/2 < m) return 0;
return 1;
}
int darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm*SQ] , gos[maxm];
int pedaret[maxm*SQ];
ll get_par(ll v){
if (pedaret[v]==v) return v;
return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st,ts;
int rp[maxm] , pr[maxm];
ll dp[maxm*SQ];
pi w[maxm];
int rw[400][400];
int dage[maxm*SQ];
map<ll,ll> mp,pm,f;
priority_queue<pi> lowq;
priority_queue<int, vector<int>, greater<int> > upq;
void bfs(int k){
q.push(k);
vis[k] = 1;
while (q.size()){
auto x = q.front();
q.pop();
for (auto m : g[x]){
if (!vis[m]) vis[m] = 1 , q.push(m) , darage[m] = darage[x] + 1;
}
}
}
vector<int> vec;
void prep(){
for (int i=1; i<=n; i++) vis[i] = darage[i] = 0;
}
void solve(ll x){
for (int i=0; i<31; i++){
if (x&(1<<i)) dp[i]++;
}
return ;
}
bool val(int x){
//cout<<x<<" ";
if (x>n/2) return 0;
for (int i=1; i<=x; i++){
//cout<<x<<" "<<pedaret[n-x+i]<<" "<<pedaret[i]<<endl;
if (pedaret[n-x+i]-pedaret[i]<m) return 0;
}
return 1;
}
string k[maxm],t[maxm];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >>n>>m;
int sq = sqrt(n)+1;
for (int i=0; i<m; i++){
cin >>rp[i]>>pr[i];
if (i==0) l = rp[i];
if (i==1) r = rp[i];
g[rp[i]].push_back(pr[i]);
}
for (int i=0; i<n*sq; i++) pedaret[i] = mod;
pedaret[l*sq] = 0;
lowq.push({0,l*sq});
while (lowq.size()){
auto x =(lowq.top()).second;
lowq.pop();
if (!vis[x]){
vis[x] = 1;
ss = x/sq , mm = x%sq;
if (mm==0){
for (auto k:g[ss]){
if (k<sq){
mid=ss*sq+k;
if(pedaret[mid]>pedaret[x]){
pedaret[mid] =pedaret[x];
lowq.push({-pedaret[mid],mid});
}
}
else{
for (int j=1; j<mod; j++){
mid=ss-k*j;
if (mid<0) break;
if (pedaret[mid*sq]>pedaret[x]+j){
pedaret[mid*sq] = pedaret[x]+j;
lowq.push({-pedaret[mid*sq],mid*sq});
}
}
for (int j = 1; j<=mod;j++){
mid=ss+k*j;
if (mid>=n) break;
if (pedaret[mid*sq]>pedaret[x]+j){
pedaret[mid*sq]=pedaret[x]+j;
lowq.push({-pedaret[mid*sq],mid*sq});
}
}
}
}
}
else{
if (pedaret[ss*sq]>pedaret[x]){
pedaret[ss*sq] = pedaret[x] , lowq.push({-pedaret[ss*sq],ss*sq});
}
if(ss-mm>=0 && pedaret[(ss-mm)*sq+mm]>pedaret[x]+1){
pedaret[(ss-mm)*sq+mm] = pedaret[x]+1;
lowq.push({-pedaret[(ss-mm)*sq+mm],(ss-mm)*sq+mm});
}
if(ss+mm<n && pedaret[(ss+mm)*sq+mm]>pedaret[x]+1){
pedaret[(ss+mm)*sq+mm] = pedaret[x]+1;
lowq.push({-pedaret[(ss+mm)*sq+mm],(ss+mm)*sq+mm});
}
}
}
}
if (pedaret[r*sq]==mod) return cout<<-1,0;
cout<<pedaret[r*sq];
}
