#include #include #define rep(i,j,n) for(ll i=j;i<(ll)(n);i++) #define rrep(i,j,n) for(ll i=j;i>=n;i--) #define all(x) (x).begin(),(x).end() #define m0(x) memset(x,0,sizeof(x)) #define pb emplace_back #define mp make_pair #define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c))) #define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()) using namespace std; using namespace atcoder; typedef long long ll; typedef unsigned long long ull; typedef long double ld; template bool chmax(T &a, const T &b){if(a bool chmin(T &a, const T &b){if(a>b) {a=b;return 1;}return 0;} const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; namespace detail { template auto make_v(std::vector& sizes, Tp const& x) { if constexpr (Nb == 1) { return std::vector(sizes[0], x); } else { size_t size = sizes[Nb-1]; sizes.pop_back(); return std::vector(size, make_v(sizes, x)); } } } // detail:: template auto make_v(size_t const(&sizes)[Nb], Tp const& x = Tp()) { std::vector s(Nb); for (size_t i = 0; i < Nb; ++i) s[i] = sizes[Nb-i-1]; return detail::make_v(s, x); } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void yn(bool ok){ if(ok) cout << "Yes\n"; else cout << "No\n"; } void solve(){ ll n,m; cin >> n >> m; vector> graph(n); rep(i,0,m){ ll u,v; cin >> u >> v; u--;v--; graph[u].pb(v); graph[v].pb(u); } ll k; cin >> k; vector stone(n,0); rep(i,0,k){ ll v; cin >> v; stone[v-1] = 1; } auto memo = make_v({n,5},LINF); queue> que; que.push({0,0,0}); while(!que.empty()){ auto [d,v,s] = que.front(); que.pop(); if(d >= memo[v][s]) continue; memo[v][s] = d; for(auto u : graph[v]){ if(stone[u]){ if(s < 4) que.push({d+1,u,s+1}); } else{ que.push({d+1,u,0}); } } } ll ans = LINF; rep(i,0,4) chmin(ans,memo[n-1][i]); if(ans == LINF) cout << "-1\n"; else cout << ans << "\n"; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll T; T = 1; /* cin >> T; */ while(T--) solve(); }