///
/// ♪ 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;
const int N = 30'010;
const int mod = 35000011;
struct mymap
{
pii* bs = new pii[0];
int v[mod] = {};
unsigned char sz[mod] = {};
int count(int x)
{
int y = x%mod;
if(!sz[y]) return 0;
Loop(i,0,sz[y])
if((bs+v[y])[i].F==x)
return 1;
return 0;
}
int& operator[](int x)
{
int y = x%mod;
if(!sz[y]) v[y] = (new pii[1])-bs, sz[y]=0;
Loop(i,0,sz[y])
if((bs+v[y])[i].F==x)
return (bs+v[y])[i].S;
if(sz[y] && (sz[y]&-sz[y]) == sz[y]){
auto tmp = new pii[sz[y]*2];
Loop(i,0,sz[y]) tmp[i] = (bs+v[y])[i];
delete[](bs+v[y]);
v[y] = tmp-bs;
}
(bs+v[y])[sz[y]++] = {x,0};
if(sz[y] > 10) exit(0);
return (bs+v[y])[sz[y]-1].S;
}
};
mymap d;
vector<int> P[N];
bool vis[N];
int n, m;
void bfs(int sv, int sp)
{
vector<int> q, q2;
vis[sv] = 1;
for(auto p : P[sv]) if(!d.count(sv<<15^p)) d[sv<<15^p] = 0, q.push_back(sv<<15^p);
if(!d.count(sv<<15^sp)) d[sv<<15^sp] = 0, 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(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
}
if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
}
u = v-p;
if(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
}
if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
}
}
q = q2;
q2.clear();
++d;
}
}
bool isPrime(int n)
{
for(int d = 2; d*d <= n; ++d)
if(n%d == 0)
return 0;
return 1;
}
int main()
{
//Loop(i,35000000,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);
}
bfs(src, p);
cout << (d.count(des<<15^dmy)? d[des<<15^dmy]: -1) << '\n';
}
