#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 200005
int n,m;
int dizi[lim][2];
set<int> st[lim];
vector<pair<int,int>> v[lim];
int vis[lim],dist[lim];
inline void dij(int bas){
for(int i=1;i<=n;i++){
vis[i]=0;
dist[i]=LLONG_MAX;
}
dist[bas]=0;
priority_queue<pair<int,int>> pq;
pq.push({0,bas});
while(pq.size()){
int node=pq.top().se;
pq.pop();
if(vis[node])continue;
vis[node]=1;
for(auto go:v[node]){
if(dist[node]!=LLONG_MAX && dist[go.fi]>dist[node]+go.se){
dist[go.fi]=dist[node]+go.se;
pq.push({-dist[go.fi],go.fi});
}
}
}
}
int32_t main(){
faster
cin>>n>>m;
int sta,tar;
for(int i=1;i<=m;i++){
cin>>dizi[i][0]>>dizi[i][1];
dizi[i][0]++;
st[dizi[i][0]].insert(dizi[i][1]);
if(i==1)sta=dizi[i][0];
else if(i==2)tar=dizi[i][0];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
int tut=abs(i-j);
for(int k=1;k*k<=tut;k++){
if(tut%k==0){
int a=k;
int b=tut/k;
//cout<<i<<" "<<j<<" "<<a<<" "<<b<<" "<<tut<<" "<<st[i].count(a)<<endl;
if(st[i].count(a)){
v[i].pb({j,b});
}
if(a!=b){
if(st[i].count(b)){
v[i].pb({j,a});
}
}
}
}
}
}
//~ FOR{
//~ cout<<v[i].size()<<endl;
//~ for(auto a:v[i])cout<<a.fi<<" "<<a.se<<endl;
//~ }
dij(sta);
//~ FOR{
//~ cout<<dist[i]<<" ";
//~ }
int cev=dist[tar];
if(cev==LLONG_MAX)cev=-1;
cout<<cev<<'\n';
return 0;
}
