#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const bool debug = false;
#define ff first
#define ss second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define YN(x) if(x)yes; else no;
#define all(X) (X).begin(), (X).end()
#define rall(X) (X).rbegin(), (X).rend()
const long long mod = 1e9 + 7;
long long mult(long long a, long long b)
{
return (a * b) % mod;
}
long long binpow(long long a, long long b) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
long long m_inverse(long long n) {
return binpow(n, mod - 2);
}
long long divide(long long a, long long b) {
return (a % mod * m_inverse(b)) % mod;
}
long long sub(long long a, long long b)
{
if (a - b >= 0)return a - b;
else return a - b + mod;
}
long long add(long long a, long long b)
{
if (a + b >= mod)return a + b - mod;
else return a + b;
}
const int LOG = 60;
const int N = 3e4;
bool vis[N][N];
int c[N], p[N];
int answ[N];
vector<int>vec[N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> c[i] >> p[i];
vec[c[i]].push_back(i);
}
for (int i = 1; i <= n; i++)
answ[i] = 1e9;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>pq;
pq.push({ 0, c[1], 1 });
vis[1][c[1]] = true;
answ[c[1]] = 0;
int ans = 1e9;
while (!pq.empty())
{
tuple<int, int, int> u = pq.top();
pq.pop();
if (get<1>(u) == c[2])
{
ans = min(ans, get<0>(u));
continue;
}
for (int d = -1; d <= 1; d += 2)
{
int nx = d * p[get<2>(u)] + get<1>(u);
if (nx >= 0 && nx <= n && !vis[get<2>(u)][nx]) {
answ[nx] = get<0>(u) + 1;
pq.push({ answ[nx], nx, get<2>(u) });
vis[get<2>(u)][nx] = true;
}
}
for (auto k : vec[get<1>(u)])
{
if (k == get<2>(u))continue;
if (!vis[k][get<1>(u)])
pq.push({ get<0>(u), get<1>(u), k });
}
}
if (ans >= 1e9)
cout << -1;
else
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
