// 2025 9/6 // 2025 9/6 #include using namespace std; #define int long long const int mod = 998244353; template void out(vector> v) { for (int i = 0; i < (int)v.size(); i++) for (int j = 0; j < (int)v.at(i).size(); j++) { cout << v.at(i).at(j) << " "; if (j == (int)v.at(i).size() - 1) cout << endl; } } template void out2(vector>> v) { cout << "-----------------" << endl; for (int i = 0; i < (int)v.size(); i++) { cout << "i:" << i << endl; for (int j = 0; j < (int)v.at(i).size(); j++) for (int k = 0; k < (int)v.at(i).at(j).size(); k++) { cout << v.at(i).at(j).at(k) << " "; if (k == (int)v.at(i).at(j).size() - 1) cout << endl; } cout << "-----------------" << endl; } } template void out3(vector>> v) { cout << "-----------------" << endl; for (int k = 0; k < (int)v.at(0).at(0).size(); k++) { cout << "k:" << k << endl; for (int i = 0; i < (int)v.size(); i++) { for (int j = 0; j < (int)v.at(i).size(); j++) { cout << v.at(i).at(j).at(k) << " "; if (j == v.at(i).size() - 1) cout << endl; } } cout << "-----------------" << endl; } } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } int power(int x, int n, int mod) { int ret = 1; while (n > 0) { if (n & 1) { ret *= x; if (mod > 0) ret %= mod; } x *= x; if (mod > 0) x %= mod; n >>= 1; } return ret; } signed main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; g.at(u).push_back(v); g.at(v).push_back(u); } int k; cin >> k; vector is(n, 0); for (int i = 0; i < k; i++) { int a; cin >> a; a--; is.at(a) = 1; } vector> dist(n, vector(5, -1)); // i番目の頂点で、岩井星人に連続してj回あっている場合の最短経路 queue> que; // (頂点番号, 連続して岩井星人に会っている回数) dist.at(0).at(0) = 0; que.push({0, 0}); while (!que.empty()) { pair p = que.front(); que.pop(); for (int u : g.at(p.first)) { if (is.at(u) == 1) { if (p.second + 1 < 5 && dist.at(u).at(p.second + 1) == -1) { dist.at(u).at(p.second + 1) = dist.at(p.first).at(p.second) + 1; que.push({u, p.second + 1}); } } else { if (dist.at(u).at(0) == -1) { dist.at(u).at(0) = dist.at(p.first).at(p.second) + 1; que.push({u, 0}); } } } } int ans = INT_MAX; for (int i = 0; i < 5; i++) { if (dist.at(n - 1).at(i) == -1) continue; chmin(ans, dist.at(n - 1).at(i)); } if (ans == INT_MAX) cout << -1 << endl; else cout << ans << endl; }