#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
int sz;
vector<vector<int>> p;
vector<vector<int>> dist;
vector<vector<bool>> vis;
priority_queue<tuple<int ,int , int>, vector<tuple<int ,int , int>> , greater<tuple<int,int ,int>>> q;
int n ;
void process(int P , int tp , int last)
{
if(P == 0)
return;
if(P > sz)
{
for(int k = 1 ; tp + k * P < n || tp - k * P >= 0 ; k++)
{
if(k*P + tp < n && dist[k * P + tp][0] > dist[tp][last] + k)
{
dist[k * P + tp][0] = dist[tp][last] + k;
q.push({dist[k * P + tp][0] , k * P + tp , 0});
}
if(tp - k * P >= 0 && dist[tp - k * P][0] > dist[tp][last] + k)
{
dist[tp - k * P][0] = dist[tp][last] + k;
q.push({dist[tp - k * P][0] , tp - k * P , 0});
}
}
}
else
{
if(P + tp < n)
{
if(dist[P + tp][P] > dist[tp][last] + 1)
{
dist[P + tp][P] = dist[tp][last] + 1;
q.push({dist[P + tp][P] , P + tp , P});
}
}
if(tp - P >= 0)
{
if(dist[tp - P][P] > dist[tp][last] + 1)
{
dist[tp - P][P] = dist[tp][last] + 1;
q.push({dist[tp - P][P] , tp - P , P});
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m;
cin>>n>>m;
sz = (int)sqrt(n);
p = vector<vector<int>> (n);
dist = vector<vector<int>> (n , vector<int>(sz +1 , INT32_MAX));
vis = vector<vector<bool>> (n , vector<bool>(sz + 1 , 0));
int trg = 0;
for(int i = 0 ; i < m; i++)
{
int a , b;
cin>>a>>b;
if(i == 0)
{
dist[a][0] = 0;
q.push({0 , a , 0});
}
if(i == 1)
{
trg = a;
}
p[a].push_back(b);
}
while(!q.empty())
{
auto [d , tp , last] = q.top();
q.pop();
if(vis[tp][last])
continue;
vis[tp][last] = 1;
for(auto P : p[tp])
{
process(P , tp , last);
}
process(last , tp , last);
}
int mn = INT32_MAX;
for(int i = 0 ; i <= sz ; i++)
{
mn = min(mn , dist[trg][i]);
}
cout<<(mn == INT32_MAX ? -1 : mn);
}
