#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
int m, n;
int piv;
vector<int> dx[30005], label[30005];
bool r_dir[30005][180], l_dir[30005][180];
int px[30005], py[30005];
vector<int> graph[30005];
int *graph0, *graph1;
bool *vis;
queue<int> pq[2];
int dijkstra(int st, int ed){
pq[0].push(st);
int dist = 0;
while (1) {
if(pq[dist%2].empty()) break;
while (!pq[dist%2].empty()) {
int qf = pq[dist%2].front();
pq[dist%2].pop();
if(qf == ed){
return dist;
}
if(vis[qf]) continue;
vis[qf] = 1;
if(qf < n){
for (auto &i : graph[qf]){
if(!vis[i]){
pq[dist%2].push(i);
}
}
}
if(qf >= n && graph0[qf] != 0 && !vis[graph0[qf] - 1]){
pq[dist%2].push(graph0[qf] - 1);
}
if(qf >= n && graph1[qf] != 0 && !vis[graph1[qf]]){
pq[(dist+1)%2].push(graph1[qf]);
}
}
dist++;
}
return -1;
}
int main(){
int st = 0, ed = 0;
scanf("%d %d",&n,&m);
for (int i=0; i<m; i++) {
int x,y;
scanf("%d %d",&x,&y);
px[i] = x;
py[i] = y;
if(i == 0){
st = x;
}
else if(i == 1){
ed = x;
}
if(y < 180){
r_dir[x][y] = 1;
l_dir[x][y] = 1;
}
else{
for (int j=0; j * y + x < n; j++) {
dx[j * y + x].push_back(y);
}
for (int j=0; j * y + x >= 0; j--) {
dx[j * y + x].push_back(-y);
}
}
}
for (int i=1; i<180; i++) {
for (int j=i; j<n; j++) {
r_dir[j][i] |= r_dir[j - i][i];
}
for (int j=n-i-1; j>=0; j--) {
l_dir[j][i] |= l_dir[j + i][i];
}
for (int j=0; j<n; j++) {
if(r_dir[j][i]){
dx[j].push_back(i);
}
if(l_dir[j][i]){
dx[j].push_back(-i);
}
}
}
piv = n;
for (int i=0; i<n; i++) {
sort(dx[i].begin(),dx[i].end());
dx[i].resize(unique(dx[i].begin(),dx[i].end()) - dx[i].begin());
for (auto &j : dx[i]){
label[i].push_back(piv++);
}
}
graph0 = (int*) calloc(piv,sizeof(int));
graph1 = (int*) calloc(piv,sizeof(int));
vis = (bool*) calloc(piv,sizeof(bool));
for(int t=0; t<m; t++){
int i = px[t];
int j = py[t];
int pos = (int)(lower_bound(dx[i].begin(),dx[i].end(),j) - dx[i].begin());
if(pos != dx[i].size() && dx[i][pos] == j){
graph[i].push_back(label[i][pos]);
}
pos = (int)(lower_bound(dx[i].begin(),dx[i].end(),-j) - dx[i].begin());
if(pos != dx[i].size() && dx[i][pos] == -j){
graph[i].push_back(label[i][pos]);
}
}
int piv = n;
for (int i=0; i<n; i++){
for (int j=0; j<dx[i].size(); j++) {
int tmp_first = i;
int tmp_second = dx[i][j];
graph0[piv++] = i+1;
if(tmp_first + tmp_second < 0 || tmp_first + tmp_second >= n) continue;
tmp_first += tmp_second;
int pos = (int)(lower_bound(dx[tmp_first].begin(),dx[tmp_first].end(),tmp_second)
- dx[tmp_first].begin());
if(pos == dx[tmp_first].size() || dx[tmp_first][pos] != tmp_second) continue;
graph1[piv - 1] = label[tmp_first][pos];
}
}
printf("%d\n",dijkstra(st,ed));
}
