import io, os
from math import *
from heapq import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, m = map(int, input().split())
edges = [[] for i in range(n)]
sussy = [[] for i in range(n)]
stuff = []
count = 0
for i in range(m):
a,b = map(int, input().split())
if count == 1:
sus = a
if count == 0:
imposter = a
sussy[a].append(b)
count += 1
for i in range(n):
for j in range(i+1,n):
for k in sussy[i]:
if i%k == j%k:
edges[i].append((j, abs(i-j)//k))
break
for k in sussy[j]:
if i%k == j%k:
edges[j].append((i, abs(i-j)//k))
break
def djk(src):
dist = [inf for i in range(n)]
dist[src] = 0
q = []
heapify(q)
heappush(q, (dist[src], src))
while len(q):
node = heappop(q)
if dist[node[1]] != node[0]:
continue
for i in edges[node[1]]:
if dist[i[0]] > node[0] + i[1]:
dist[i[0]] = node[0] + i[1]
heappush(q, (node[0]+i[1], i[0]))
return dist
susz = djk(imposter)[sus]
print(-1 if susz == inf else susz)
