#-*- coding: utf-8 -*-
from heapq import *
from bisect import bisect_right
maxint = int(2E9)
class Node(object):
def __init__(self, u, dist):
self.u = u
self.dist = dist
def __cmp__(self, other):
return cmp(self.dist, other.dist)
def binary_search(L, val):
if not L : return False
s = bisect_right(L, val)
return L[s-1] == val
def dijkstra(start):
global N, M, V, B, P
dist = [maxint for i in range(N)]
start = B[0]
dist[start] = 0
Q = []
heappush(Q, Node(start, 0))
while Q :
#### priority queue is not empty ####
node = heappop(Q)
u, dist_u = node.u, node.dist
if dist_u > dist[u] : continue
for power in V[u]:
#### u에 power 만큼의 힘을 가진 도게가 있음 ####
#### 오른쪽으로 탐색을 진행 ####
to = u+power
cost = dist_u + 1
while to < N : #### 목적지의 빌딩번호가 N보다 커지면 안됨 ####
if dist[to] > cost :
dist[to] = cost
heappush(Q, Node(to, cost))
if binary_search(V[to], power):
"""
V[o]에 p만큼의 힘을 가진 도게가 있으므로,
이 도게가 더 가는 것이나 이미 V[o]에 있는 도게가 더 가는 것이나
equivalent함
따라서, 중복탐색을 하지 않는 것이 더 효율적임
"""
break
to += power
cost += 1
#### 왼쪽으로 탐색을 진행 ####
to = u-power
cost = dist_u + 1
while to >= 0 : #### 목적지의 빌딩번호가 0보다 작아지면 안됨 ####
if dist[to] > cost :
dist[to] = cost
heappush(Q, Node(to, cost))
if binary_search(V[to], power):
"""
V[o]에 p만큼의 가진 도게가 있으므로 이 도게가 더 가는 것이나
V[o]에 있는 도게가 더 가는 것이나 equivalent함
따라서, 중복탐색을 하지 않는 것이 더 효율적임
"""
break
to -= power
cost += 1
return dist
def main():
global N, M, V, B, P
"""
V : VERTICES의 집합; V[i][j]는 i라는 빌딩에서 j라는 power를 가진게 있다는걸 의미함
P : POWER; B : BUILDING;
"""
N, M = map(int, raw_input().split())
V = [ [] for i in range(N) ]
B = [None for i in range(M)]
P = [None for i in range(M)]
for i in range(M):
B[i], P[i] = map(int, raw_input().split())
V[B[i]].append(P[i])
for i in range(N):
V[i] = list(set(V[i]))
V[i].sort()
start = B[0]
dist = dijkstra(start)
ans = dist[B[1]]
if ans == maxint: print -1
else: print ans
return
main()
