#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define INF 1e9
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;
int n,m;
vector<vi> ns;
bitset<30001> dp[30001],vis;
queue<pair<ii,int> > q;
void solve(int pos, int u, int d, int p){
if(pos<0 || pos>=n) return;
if(dp[pos][p]) return;
dp[pos][p]=true;
q.push(mp(mp(d+1,pos),p));
}
void add(int u, int d){
for(int i:ns[u]){
if(!dp[u][i]);
q.push(mp(mp(d,u),i));
}
vis[u]=true;
}
int main(){
//printf("here\n");
scanf("%d%d",&n,&m);
ns.assign(n+2,vi());
int n1;
int nf;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(!i) n1=x;
if(i==1) nf=x;
ns[x].pb(y);
//jm[i]=y;
}
//for(int i=0;i<n;i++) printf("%d ", dis[n1][i]); printf("\n");
for(int i:ns[n1]){
dp[n1][i]=true;
q.push(mp(mp(0,n1),i));
}
while(!q.empty()){
int u=q.front().fi.se;
int d=q.front().fi.fi;
int p=q.front().se;
q.pop();
if(u==nf){
printf("%d\n", d);
return 0;
}
solve(u+p,u,d,p);
//printf("%d %d\n",u,p);
solve(u-p,u,d,p);
if(!vis[u]) add(u,d);
}
//printf("%d %d\n", n1,nf);
printf("-1\n");
return 0;
}
