#ifndef MY_HEADER #define MY_HEADER #include #include using namespace std; using namespace atcoder; using lint = long long; using ulint = unsigned long long; using llint = __int128_t; struct edge; using graph = vector>; #define endl '\n' constexpr int INF = 1<<30; constexpr lint INF64 = 1LL<<61; constexpr lint mod107 = 1e9+7; using mint107 = modint1000000007; constexpr long mod = 998244353; using mint = modint998244353; lint ceilDiv(lint x, lint y){if(x >= 0){return (x+y-1)/y;}else{return x/y;}} lint floorDiv(lint x, lint y){if(x >= 0){return x/y;}else{return (x-y+1)/y;}} lint Sqrt(lint x) {assert(x >= 0); lint ans = sqrt(x); while(ans*ans > x)ans--; while((ans+1)*(ans+1)<=x)ans++; return ans;} lint gcd(lint a,lint b){if(a 0){int a = n%10;char b = '0' + a;string c = "";c += b;n /= 10;ans = c + ans;}}return ans;} string toString(lint n, lint k){string ans = toString(n);string tmp = "";while(ans.length() + tmp.length() < k){tmp += "0";}return tmp + ans;} vectorprime;void makePrime(lint n){prime.push_back(2);for(lint i=3;i<=n;i+=2){bool chk = true;for(lint j=0;j= 0; i--) #define vec vector #define pb push_back #define eb emplace_back #define se second #define fi first #define al(x) x.begin(),x.end() #define ral(x) x.rbegin(),x.rend() struct edge{ edge(lint v, lint c = 1) {to = v, cost = c;} lint to; lint cost; }; #endif #ifndef MY_HEADER #define MY_HEADER #include using namespace std; struct edge{ int to; long long cost; }; #define vec vector using lint = long long; constexpr long long INF64 = 1LL<<61; using graph = vector>; #endif vectordijkstra(int s, graph &g) { vecret(g.size(), INF64); priority_queue>que; que.push({-0, s}); ret[s] = 0; vecwent(g.size(), false); while(!que.empty()) { auto q = que.top(); que.pop(); if(went[q.second]) continue; went[q.second] = true; ret[q.second] = -q.first; for(auto&& e: g[q.second]) { if(ret[e.to] > -q.first + e.cost) { ret[e.to] = -q.first + e.cost; que.push({-ret[e.to], e.to}); } } } return ret; } int main(){ lint N, M; cin >> N >> M; graph G(N*6); vecu(M), v(M); rep(i, M) { cin >> u[i] >> v[i]; u[i]--;v[i]--; } int K;cin >> K; vecmp(100000,false); rep(i, K) { int a;cin >> a; mp[a-1] = true; } rep(i, M) { rep(j, 5) { if(mp[v[i]]) { G[u[i] + N*j].eb(v[i] + N*(j+1)); }else { G[u[i] + N*j].eb(v[i] ); } if(mp[u[i]]) { G[v[i] + N*j].eb(u[i] + N*(j+1)); }else { G[v[i] + N*j].eb(u[i]); } } } auto d = dijkstra(0, G); lint ans = INF64; rep(i, 5 ) ans = min(ans, d[N-1 + N*i]); if(ans == INF64) ans = -1; cout << ans; }