import heapq # 入力 N, M = map(int, input().split()) A, B = [ None ] * M, [ None ] * M for i in range(M): A[i], B[i] = map(int, input().split()) # 隣接リストの作成 → グラフの辺を追加 G = [ list() for i in range(N + 1) ] for i in range(M): G[A[i]].append((B[i], 1)) def dijkstra(beg): # ダイクストラ法:配列の初期化など dist = [ 10 ** 19 ] * (N + 1) used = [ False ] * (N + 1) Q = list() dist[beg] = 0 heapq.heappush(Q, (0, beg)) # ダイクストラ法:優先度付きキューの更新 while len(Q) >= 1: pos = heapq.heappop(Q)[1] if used[pos] == True: continue used[pos] = True for i in G[pos]: to = i[0] cost = dist[pos] + i[1] if dist[to] > cost: dist[to] = cost heapq.heappush(Q, (dist[to], to)) return dist dist1 = dijkstra(1) dist2 = dijkstra(N - 1) dist3 = dijkstra(N) if min(dist1[N - 1] + dist2[N] + dist3[1], dist1[N] + dist3[N - 1] + dist2[1]) < 10 ** 19: print(min(dist1[N - 1] + dist2[N] + dist3[1], dist1[N] + dist3[N - 1] + dist2[1])) else: print(-1)