///
/// ♪ Pizza mozzarella rella rella rella... ♪
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int N = 30'010;
const int mod = 10000019;
struct myset
{
int v[mod][4] = {};
unsigned char sz[mod] = {};
int sum = 0;
bool add(int x)
{
++sum;
if(sum > 10'000'000) exit(0);
int y = x%mod;
Loop(i,0,sz[y])
if(v[y][i]==x)
return 0;
if(sz[y] == 4) exit(0);
v[y][sz[y]++] = x;
return 1;
}
};
myset d;
vector<int> P[N];
bool vis[N];
int n, m;
int bfs(int sv, int sp, int des)
{
if(sv == des) return 0;
vector<int> q, q2;
vis[sv] = 1;
for(auto p : P[sv]) if(d.add(sv<<15^p)) q.push_back(sv<<15^p);
if(d.add(sv<<15^sp)) q.push_back(sv<<15^sp);
for(int d = 0; q.size();)
{
for(ull i = 0; i < q.size(); ++i)
{
int v = q[i]>>15, p = q[i]&32767;
//cerr << v << ' ' << p << ": " << d << '\n';
int u = v+p;
if(u == des) return d+1;
if(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
u = v-p;
if(u == des) return d+1;
if(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
}
q = q2;
q2.clear();
++d;
}
return -1;
}
bool isPrime(int n)
{
for(int d = 2; d*d <= n; ++d)
if(n%d == 0)
return 0;
return 1;
}
int main()
{
//Loop(i,10000000,INT_MAX) if(isPrime(i)){cout << i;break;}
FAST;
cin >> n >> m;
int p, src, des, dmy;
cin >> src >> p;
cin >> des >> dmy;
P[des].push_back(dmy);
Loop(i,2,m)
{
int v, p;
cin >> v >> p;
P[v].push_back(p);
}
cout << bfs(src, p, des) << '\n';
}
