#include #include using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128; using P = pair; template using vc = vector; template using vv = vc>; using vl = vc; using vvl = vc>; using vvb = vc>; using vul = vc; using vs = vc; using vb = vc; #define rep(i,s,n) for(ll i=s;i<(n);i++) #define Rep(i,s,n) for(ll i=n;i>=s;i--) #define nall(x) x.begin(),x.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define pob pop_back #define nexp(v) next_permutation(v) #define prep(v) prev_permutation(v) #define YES cout<<"Yes"<b)a=b;} void chmax(ll &a,ll b){if(a1)res-=res/n; return res; } vs rotate90(const vs& g){ //正方形を90度右回転 ll len=g.size(); vs x(len,string(len,'.')); rep(i,0,len){ rep(j,0,len){ x[j][len-1-i]=g[i][j]; } } return x; } vl Eratos(ll n){ //篩 vc isprime(n+1,true); isprime[0]=isprime[1]=false; for(ll i=2;i*i<=n;i++){ if(isprime[i]){ for(int j=i*i;j<=n;j+=i)isprime[j]=false; } } vl primes; for(ll i=2;i<=n;i++){ if(isprime[i])primes.pb(i); } return primes; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n,m; cin >> n >> m; set ex; vvl g(n); rep(i,0,m){ ll u,v; cin >> u >> v; u--;v--; g[u].pb(v); g[v].pb(u); } ll k; cin >> k; rep(i,0,k){ ll a; cin >> a; a--; ex.insert(a); } vvb visited(n,vb(5,false)); visited[0][0]=true; ll ans=INF; queue> q; q.push({0,0,0}); while(!q.empty()){ auto [now,iwhy,step]=q.front(); q.pop(); if(now==n-1){ cout << step << endl; return 0; } for(auto next:g[now]){ ll ni=ex.contains(next)?iwhy+1:0; if(ni>4)continue; if(visited[next][ni])continue; visited[next][ni]=true; q.push({next,ni,step+1}); } } cout << -1 << endl; }