#include #include using namespace atcoder; using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define ALL(a) (a).begin(), (a).end() #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = (n) - 1; i >= 0; --i) #define foreach(i, n) for (auto i : (n)) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define popcount __builtin_popcountll using mint = modint998244353; using mint1 = modint1000000007; template using umap = std::unordered_map; template using uset = std::unordered_set; // 参考元 : https://qiita.com/ganyariya/items/df35d253726269bda436 struct HashPair { //注意 constがいる template size_t operator()(const pair &p) const { //first分をハッシュ化する auto hash1 = hash{}(p.first); //second分をハッシュ化する auto hash2 = hash{}(p.second); //重複しないようにハッシュ処理 size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; template using pair_map = unordered_map, ll, HashPair>; template using pair_set = unordered_set, HashPair>; template using v = vector; template using vv = v>; template using vvv = vv>; template using P = pair; using grid = vector>; using graph = vector>; using vi = vector; using vvi = vector>; using vvvi = vector>>; using vl = vector; using vvl = vector>; using vvvl = vector>>; using vm = vector; using vvm = vector>; using vvvm = vector>>; using vm1 = vector; using vvm1 = vector>; using vvvm1 = vector>>; using vld = vector; using vvld = vector>; using vvvld = vector>>; using vb = vector; using vvb = vector>; using vs = vector; using vvs = vector>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m; cin >> n >> m; graph g(n); rep(i, m) { ll u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } ll k; cin >> k; uset iwai; rep(i, k) { ll a; cin >> a; a--; iwai.insert(a); } vvl dist(n, vl(5, -1)); queue> que; dist[0][0] = 0; que.push({0, 0}); while (!que.empty()) { auto [v, iwi] = que.front(); que.pop(); foreach(nv, g[v]) { ll next_iwi = iwi; if (iwai.count(nv)) { next_iwi++; } else { next_iwi = 0; } if (next_iwi > 4) continue; if (dist[nv][next_iwi] != -1) continue; dist[nv][next_iwi] = dist[v][iwi] + 1; que.push({nv, next_iwi}); } } cout << dist[n - 1][0] << "\n"; return 0; }