#include using namespace std; using namespace chrono; using Clock = steady_clock; #include using namespace atcoder; using vi = vector; using vvi = vector>; using vvvi = vector>>; using ll = long long; using vl = vector; using vvl = vector>; using vvvl = vector>>; using vvvvl = vector>>>; using vb = vector; using vvb = vector>; using vvvb = vector>>; using str = string; using vs = vector; using ull = unsigned long long; using lll = __int128; using pii = pair; using pll = pair; using ld = long double; template using vc = vector; template using vv = vector>; template using vvv = vector>>; template using vvvv = vector>>>; template using pq = priority_queue; template using pq_min = priority_queue, greater>; #define rep(i, n) for(int i = 0; i < (n); i++) #define rep2(i, a, b) for(int i = (a); i <= (b); i++) #define drep(i, a, b) for(int i = (a); i >= (b); i--) #define crep(c, a, b) for(char c = a; c <= b; c++) #define ALL(v) v.begin(), v.end() #define NPer(v) next_permutation(ALL(v)) vi Iota(int n, int a = 0) { vi v(n); iota(ALL(v), a); return v; } template void Sort(vc& v) { sort(ALL(v)); } void Sort(str& s) { sort(ALL(s)); } template void rSort(vc& v) { sort(v.rbegin(), v.rend()); } void rSort(str& s) { sort(s.rbegin(), s.rend()); } template int Uniq(vc& v) { Sort(v); v.erase(unique(ALL(v)), v.end()); return (int)ssize(v); } void Uniq(str& s) { Sort(s); s.erase(unique(ALL(s)), s.end()); } template void Rev(vc& v) { reverse(ALL(v)); } void Rev(str& s) { reverse(ALL(s)); } inline ll max(ll a, ll b) { return (a > b ? a : b); } inline ll min(ll a, ll b) { return (a < b ? a : b); } template inline bool chmax(T& a, const U& b) { if(a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, const U& b) { if(a > b) { a = b; return true; } return false; } inline ll popcnt(ll x) { return __builtin_popcountll(x); } template inline ll dot(const P& p, const P& q) { return (ll)p.first * q.first + (ll)p.second * q.second; } template inline ll cross(const P& p, const P& q) { return (ll)p.first * q.second - (ll)p.second * q.first; } //--------------------------------!!YNはここ!!--------------------------------// inline void YN(bool b, const str& yes = "Yes", const str& no = "No") { cout << (b ? yes : no) << "\n"; } void YN(const vb& v, const str& yes = "Yes", const str& no = "No") { for(auto b : v) { YN(b, yes, no); } } constexpr ll INF = 1e18; constexpr int inf = 1e9; inline void YNinf(ll x, ll a = INF) { cout << (x < a ? x : -1) << "\n"; } inline void YNinf2(ll x, ll a = -INF) { cout << (x > a ? x : -1) << "\n"; } //----------------------------------------------------------------------------// template istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template ostream& operator<<(ostream& os, const pair& p) { os << p.first << ' ' << p.second; return os; } template istream& operator>>(istream& is, vc& v) { for(auto& x : v) { is >> x; } return is; } template ostream& operator<<(ostream& os, const vc& v) { rep(i, (ll)ssize(v)) { if(i) { os << ' '; } os << v[i]; } return os; } template T vsum(const vc& v) { T sum = 0; for(auto a : v) { sum += a; } return sum; } inline ll div_floor(ll a, ll b) { if(b < 0) { return div_floor(-a, -b); } ll res = a / b; res -= (a % b < 0); return res; } inline ll div_ceil(ll a, ll b) { if(b < 0) { return div_ceil(-a, -b); } ll res = a / b; res += (a % b > 0); return res; } inline ll gcd(const vl& v) { ll res = 0; for(auto x : v) { res = gcd(res, x); } return res; } inline ll lcm(const vl& v) { ll res = 1; for(auto x : v) { res = lcm(res, x); } return res; } template inline int idx(const vc& v, const T& x) { auto it = lower_bound(ALL(v), x); return (it != v.end() && *it == x ? it - v.begin() : -1); } template int comp(vc& v, int a = 0) { auto X = v; Uniq(X); for(auto& x : v) { x = idx(X, x) + a; } return (int)ssize(X); } template Iter bs(Iter l, Iter r, const F& cmp) { if(l == r) { return l; } while(r - l > 1) { Iter m = l + (r - l) / 2; if(cmp(*m)) { r = m; } else { l = m; } } return (cmp(*l) ? l : r); } inline bool Outside(ll i, ll j, ll H, ll W) { return i < 0 || i >= H || j < 0 || j >= W; } void extGCD(ll a, ll b, ll& x, ll& y) { if(b == 0) { x = 1; y = 0; return; } extGCD(b, a % b, y, x); y -= a / b * x; } //--------------------------------!!Modはここ!!--------------------------------// constexpr int Mod = 998244353; // constexpr int Mod = 1000000007; // int Mod = 998244353; using mint = modint998244353; // using mint = modint1000000007; // using mint = modint; const int inv2 = (Mod + 1) / 2; //-----------------------------------------------------------------------------// //-----------------------------ヒューリスティック用-----------------------------// struct TimeKeeper { Clock::time_point start; ld time_limit; TimeKeeper(ld tl = 1900) { time_limit = tl; start = Clock::now(); } ld elapsed() const { auto now = Clock::now(); return duration(now - start).count(); } bool isTimeOver() const { return elapsed() >= time_limit; } ld progress() const { return min(elapsed() / time_limit, ld(1.0)); } }; bool anneal_accept(TimeKeeper& tk, mt19937_64& rng, ld diff) { if(diff >= 0) { return true; } ld start_temp = 100, end_temp = 1; ld prg = tk.progress(); ld temp = start_temp * pow(end_temp / start_temp, prg); ld prob = exp(diff / temp); ld r = (ld)rng() / rng.max(); return r < prob; } //------------------------------------------------------------------------------// struct UF { int N, C; vi Par, Size, Edge; UF(int n) { N = n; C = n; Par = Iota(N + 1); Size.resize(N + 1, 1); Edge.resize(N + 1, 0); } int root(int x) { return (Par[x] == x ? x : Par[x] = root(Par[x])); } bool same(int x, int y) { return root(x) == root(y); } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) { Edge[x]++; return false; } Par[y] = x; Size[x] += Size[y]; Edge[x] += Edge[y] + 1; C--; return true; } }; struct Rational { ll num, den; Rational (lll n = 0, lll d = 1) { if(d < 0) { n *= -1; d *= -1; } lll GCD = gcd(n, d); num = n / GCD; den = d / GCD; } Rational operator+(const Rational& other) const { return Rational((lll)num * other.den + (lll)den * other.num, (lll)den * (lll)other.den); } Rational& operator+=(const Rational& other) { return *this = *this + other; } Rational operator-(const Rational& other) const { return Rational((lll)num * other.den - (lll)den * other.num, (lll)den * (lll)other.den); } Rational& operator-=(const Rational& other) { return *this = *this - other; } Rational operator*(const Rational& other) const { return Rational((lll)num * other.num, (lll)den * other.den); } Rational& operator*=(const Rational& other) { return *this = *this * other; } Rational operator/(const Rational& other) const { return Rational((lll)num * other.den, (lll)den * other.num); } Rational& operator/=(const Rational& other) { return *this = *this / other; } bool operator==(const Rational& other) const { return num == other.num && den == other.den; } bool operator!=(const Rational& other) const { return !(*this == other); } bool operator<(const Rational& other) const { return (lll)num * other.den < (lll)den * other.num; } bool operator<=(const Rational& other) const { return (*this == other) || (*this < other); } bool operator>(const Rational& other) const { return !(*this <= other); } bool operator>=(const Rational& other) const { return !(*this < other); } }; struct Hash { const vl M = { 1000000007, 1000000009 }; const vi B = { 1007, 1009 }; int N; vvl H, RH, powB = { { 1 }, { 1 } }; Hash(const str& s) { N = ssize(s); auto rs = s; Rev(rs); rep(t, 2) { while(ssize(powB[t]) <= N) { powB[t].push_back(powB[t].back() * B[t] % M[t]); } } H.resize(2, vl(N + 1, 0)); RH.resize(2, vl(N + 1, 0)); rep(i, N) rep(t, 2) { H[t][i + 1] = (H[t][i] * B[t] + s[i]) % M[t]; RH[t][i + 1] = (RH[t][i] * B[t] + rs[i]) % M[t]; } } pll get(const vvl& h, int l, int r) { // 0-index, [l, r) ll h1 = (h[0][r] - h[0][l] * powB[0][r - l] % M[0] + M[0]) % M[0]; ll h2 = (h[1][r] - h[1][l] * powB[1][r - l] % M[1] + M[1]) % M[1]; return { h1, h2 }; } bool palindrome(int l, int r) { int rl = N - r, rr = N - l; return get(H, l, r) == get(RH, rl, rr); } }; struct Trie { struct Node { array next; int cnt, end; Node() { next.fill(-1); cnt = end = 0; } }; vc trie; Trie() { trie.emplace_back(); } void insert(const str& s) { int now = 0; for(auto c : s) { int next = trie[now].next[c - 'a']; if(next == -1) { next = ssize(trie); trie[now].next[c - 'a'] = next; trie.emplace_back(); } now = next; trie[now].cnt++; } trie[now].end++; } int prefix_cnt(const str& s) { int now = 0; for(auto c : s) { int next = trie[now].next[c - 'a']; if(next == -1) { return 0; } now = next; } return trie[now].end; } int LCP(const str& s) { int len = ssize(s); int now = 0; rep(i, len) { int next = trie[now].next[s[i] - 'a']; if(next == -1) { return i; } now = next; } return len; } }; struct Dinic { struct Edge { int to, rev; ll cap; }; using Graph = vv; Graph G; vi dist, iter; Dinic(int n): G(n), dist(n), iter(n) {} void add_edge(int from, int to, ll cap = 1) { Edge F, T; F.to = to; F.cap = cap; F.rev = ssize(G[to]); T.to = from; T.cap = 0; T.rev = ssize(G[from]); G[from].push_back(F); G[to].push_back(T); } bool bfs(int s, int t) { fill(ALL(dist), -1); dist[s] = 0; queue Q; Q.push(s); while(!Q.empty()) { auto v = Q.front(); Q.pop(); for(auto& e : G[v]) { if(e.cap > 0 && dist[e.to] == -1) { dist[e.to] = dist[v] + 1; Q.push(e.to); } } } return dist[t] != -1; } ll dfs(int v, int t, ll lim = INF) { if(v == t) { return lim; } for(int& i = iter[v]; i < (int)ssize(G[v]); i++) { auto& e = G[v][i]; if(e.cap > 0 && dist[e.to] == dist[v] + 1) { ll f = dfs(e.to, t, min(e.cap, lim)); if(f > 0) { e.cap -= f; G[e.to][e.rev].cap += f; return f; } } } return 0; } ll max_flow(int s, int t) { ll flow = 0; while(bfs(s, t)) { fill(ALL(iter), 0); while(1) { ll f = dfs(s, t); if(f == 0) { break; } flow += f; } } return flow; } }; ll Pow(ll a, ll k, ll mod = Mod) { ll res = 1; a = (a % mod + mod) % mod; while(k) { if(k % 2 == 1) { res = res * a % mod; } a = a * a % mod; k /= 2; } return res; } ll inv(ll a, ll mod = Mod) { return Pow(a, mod - 2, mod); } vi toBase(ll x, int n = 2) { assert(n > 1); assert(x >= 0); if(x == 0) { return { 0 }; } vi res; while(x) { res.push_back(x % n); x /= n; } Rev(res); return res; } ll vp(ll x, ll p) { assert(p > 1); const ll INF = 1e18; if(x == 0) { return INF; } if(x < 0) { return vp(-x, p); } ll res = 0; while(x % p == 0) { x /= p; res++; } return res; } vc> RL(const str& s) { vc> res; if(s.empty()) { return res; } char prev = s[0]; int cnt = 0; for(auto c : s) { if(c == prev) { cnt++; } else { res.emplace_back(prev, cnt); prev = c; cnt = 1; } } res.emplace_back(prev, cnt); return res; } template void arg_sort(vc& XY) { auto cmp = [](const T& p, const T& q) -> bool { auto [px, py] = p; auto [qx, qy] = q; bool a = (py > 0) || (py == 0 && px > 0); bool b = (qy > 0) || (qy == 0 && qx > 0); if(a != b) { return a; } return cross(p, q) > 0; }; sort(ALL(XY), cmp); } template ll Inversion(vc A) { int n = ssize(A); int K = comp(A); ll res = 0; fenwick_tree bit(K); rep(i, n) { res += bit.sum(A[i] + 1, K); bit.add(A[i], 1); } return res; } const vc d4 = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; const vc d8 = { { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } }; void solve() { int N, M; cin >> N >> M; vvi G(N + 1); while(M--) { int u, v; cin >> u >> v; G[u].emplace_back(v); G[v].emplace_back(u); } int K; cin >> K; bitset<100010> yiwiy; while(K--) { int a; cin >> a; yiwiy[a] = 1; } constexpr int Y = 5; vvi dist(N + 1, vi(Y, inf)); dist[1][0] = 0; queue que; que.emplace(1, 0); while(!que.empty()) { auto [x, y] = que.front(); que.pop(); for(int nx : G[x]) { int ny = (yiwiy[nx] ? y + 1 : 0); if(ny < Y && chmin(dist[nx][ny], dist[x][y] + 1)) { que.emplace(nx, ny); } } } YNinf(dist[N][0], inf); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20); int T = 1; // cin >> T; while(T--) { solve(); } }