#重みのないグラフでの最短経路問題 #隣接リストと始点を与えると始点からの距離のリスト & 親のリストを返す from collections import deque def NC_Dij(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 q = deque([start]) plis = [i for i in range(len(lis))] while len(q) > 0: now = q.popleft() for nex in lis[now]: if ret[nex] > ret[now] + 1: ret[nex] = ret[now] + 1 plis[nex] = now q.append(nex) return ret,plis #重み有グラフの最短経路問題 #隣接リストは[隣接点,コスト]で入っていること #負の重不可 import heapq def Dijkstra(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 end_flag = [False] * len(lis) end_num = 0 q = [(0,start)] while len(q) > 0: ncost,now = heapq.heappop(q) if end_flag[now]: continue end_flag[now] = True end_num += 1 if end_num == len(lis): break for nex,ecost in lis[now]: if ret[nex] > ncost + ecost: ret[nex] = ncost + ecost heapq.heappush(q , (ret[nex] , nex)) return ret N,M = map(int,input().split()) e = [] for i in range(M): u,v = map(int,input().split()) u -= 1 v -= 1 e.append((u,v)) K = int(input()) if K != 0: A = list(map(int,input().split())) Aset = set( [x-1 for x in A]) else: Aset = set() lis = [ [] for i in range(N*5) ] for u,v in e: if v not in Aset: for i in range(5): lis[i*N+u].append(v) else: for i in range(4): lis[i*N+u].append( (i+1)*N+v ) if u not in Aset: for i in range(5): lis[i*N+v].append(u) else: for i in range(4): lis[i*N+v].append( (i+1)*N+u ) dlis,_ = NC_Dij(lis,0) # print (dlis) ans = float("inf") for i in range(5): ans = min(ans, dlis[i*N+N-1] ) if ans == float("inf"): ans = -1 print (ans)