#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=2005;
vector<int> v[nmax];
pair<int,int> q[2][nmax*nmax];
int d[nmax][nmax];
int p[2],u[2];
int n,m,i,j,wh,x,cost,use,fin,k;
void prp(int a,int b,int dist,int wh)
{
if(dist<d[a][b])
{
d[a][b]=dist;
q[wh][++u[wh]]={a,b};
}
}
int dij()
{
p[0]=u[0]=1;
for(cost=0;cost<=n*n;cost++)
{
p[1-use]=1;u[1-use]=0;
while(p[use]<=u[use])
{
i=q[use][p[use]].first;j=q[use][p[use]].second;
++p[use];
if(i==fin)
return cost;
if(i-j>=0) prp(i-j,j,cost+1,1-use);
if(i+j<n) prp(i+j,j,cost+1,1-use);
for(k=0;k<v[i].size();k++)
prp(i,v[i][k],cost,use);
}
use=1-use;
}
return -1;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(i=0;i<n;i++)
for(j=1;j<=n;j++)
d[i][j]=2*n*n;
for(i=0;i<n;i++)
{
cin>>wh>>x;
v[wh].push_back(x);
if(i==0)
q[0][1]={wh,x},d[wh][x]=0;
if(i==1)
fin=wh;
}
cout<<dij();
return 0;
}
