#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=30010;
const int mxM=8000000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N, M;
vector <int> v[mxN];
map <short, int> mp[mxN];
vector <pair<int, bool>> adj[mxM];
int idx;
int X, Y;
list <int> lst;
int dis[mxM];
bool Chk[mxM];
void zero_one_bfs()
{
while(!lst.empty())
{
int now=lst.front();
lst.pop_front();
if(Chk[now]) continue;
Chk[now]=true;
for(pii nxt : adj[now])
{
if(dis[nxt.fir]>dis[now]+nxt.sec)
{
dis[nxt.fir]=dis[now]+nxt.sec;
if(lst.empty() || dis[lst.front()]<=dis[nxt.fir]) lst.push_front(nxt.fir);
else lst.push_back(nxt.fir);
}
}
}
}
int main()
{
gibon
cin >> N >> M;
idx=N;
for(int i=1;i<=M;i++)
{
int b, p;
cin >> b >> p;
if(i==1) X=b;
if(i==2) Y=b;
if(mp[b].end()==mp[b].find(p))
{
for(int j=b%p;j<N;j+=p)
{
mp[j][p]=idx;
if(j>=p)
{
adj[idx].push_back({idx-1, 1});
adj[idx-1].push_back({idx, 1});
}
idx++;
}
}
v[b].push_back(p);
}
for(int i=0;i<N;i++)
{
for(auto iter=mp[i].begin();iter!=mp[i].end();iter++)
{
adj[iter->sec].push_back({i, 0});
}
for(int nxt : v[i])
{
adj[i].push_back({mp[i][nxt], 0});
}
}
for(int i=0;i<idx;i++)
{
dis[i]=MOD;
}
dis[X]=0;
lst.push_front(X);
zero_one_bfs();
if(dis[Y]==MOD) cout << -1;
else cout << dis[Y];
}
