//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

int n, m;

int d[maxn];

vector<int> G[maxn];

bool have[maxn][ + ];

int s, t;

bool vis[maxn];

int solve(){

    queue<int> que;

    memset(d, 0x7f, sizeof(d));

    d[s] = ;

    que.push(s);

    while (!que.empty()){

        int u = que.front();

        que.pop();

        vis[u] = false;

        for (int i = ; i < G[u].size(); i++){

            int step = G[u][i];

            for (int j = ; u + step * j < n; j++){

                int v = u + step * j;

                if (d[v] > d[u] + j){

                    d[v] = d[u] + j;

                    if (!vis[v]){

                        que.push(v);

                        vis[v] = true;

                    }

                }

                if (step <=  && have[v][step]) break;

            }

            for (int j = ; u - step * j >= ; j++){

                int v = u - step * j;

                if (d[v] > d[u] + j){

                    d[v] = d[u] + j;

                    if (!vis[v]){

                        que.push(v);

                        vis[v] = true;

                    }

                }

                if (step <=  && have[v][step]) break;

            }

        }

    }

    return d[t] == 0x7f7f7f7f ? - : d[t];

}

int main(){

    cin >> n >> m;

    for (int i = ; i < m; i++){

        int a, b; scanf("%d%d", &a, &b);

        if (i == ) s = a;

        if (i == ) t = a;

        G[a].pb(b);

        if (b <= ) have[a][b] = ;

    }

    for (int i = ; i < n; i++){

        sort(ALL(G[i]));

        G[i].erase(unique(ALL(G[i])), G[i].end());

    }

    printf("%d\n", solve());

    return ;

}