///
/// ♪ 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;
unordered_map<int,int> d;
vector<int> P[N];
bool vis[N];
int n, m;
void bfs(int sv, int sp)
{
vector<int> q;
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 i = 0, j = q.size(), d = 0; i < q.size(); j = q.size(), ++d) for(; i < j; ++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, q.push_back(u<<15^p);
}
if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.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, q.push_back(u<<15^p);
}
if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.push_back(u<<15^p);
}
}
}
int main()
{
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';
}
