#line 2 "library/template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; #ifdef LOCAL #include #else template concept Streamable = requires(ostream os, T &x) { os << x; }; template concept is_modint = requires(mint &x) { { x.val() } -> std::convertible_to; }; #define debug(...) #endif template void print_one(const T &value) { cout << value; } template void print_one(const T &value) { cout << value.val(); } void print() { cout << '\n'; } template void print(const T &a, const Ts &...b) { print_one(a); ((cout << ' ', print_one(b)), ...); cout << '\n'; } template requires(!Streamable) void print(const Iterable &v) { for(auto it = v.begin(); it != v.end(); ++it) { if(it != v.begin()) cout << " "; print_one(*it); } cout << '\n'; } using vi = vector; using vii = vector>; using pii = pair; using ll = long long; using vl = vector; using vll = vector; using pll = pair; #define all(v) begin(v), end(v) template void UNIQUE(T &v) { ranges::sort(v); v.erase(unique(all(v)), end(v)); } template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // https://trap.jp/post/1224/ template constexpr auto min(T... a) { return min(initializer_list>{a...}); } template constexpr auto max(T... a) { return max(initializer_list>{a...}); } template void input(T &...a) { (cin >> ... >> a); } template void input(vector &a) { for(T &x : a) cin >> x; } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1_0(n, c) REP1_1(n, c) #define REP1_1(n, c) \ for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++) #define REP1(n) REP1_0(n, __COUNTER__) #define REP2(i, a) for(ll i = 0; i < (ll)(a); i++) #define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++) #define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; template constexpr T floor(T x, T y) noexcept { return x / y - ((x ^ y) < 0 and x % y); } template constexpr T ceil(T x, T y) noexcept { return x / y + ((x ^ y) >= 0 and x % y); } // yの符号に関わらず非負で定義 \bmod:texコマンド template constexpr T bmod(T x, T y) noexcept { T m = x % y; return (m < 0) ? m + (y > 0 ? y : -y) : m; } template constexpr int bit_width(T x) noexcept { return std::bit_width((uint64_t)x); } template constexpr int popcount(T x) noexcept { return std::popcount((uint64_t)x); } constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; } #line 3 "library/graph/graph-template.hpp" /** * @brief Graph Template(グラフテンプレート) * @see https://ei1333.github.io/library/graph/graph-template.hpp */ template struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} Edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template struct Graph { using cost_type = T; vector>> g; int es; // edge_size Graph() = default; explicit Graph(int n) : g(n), es(0) {}; int size() const { return ssize(g); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } vector> &operator[](const int &k) { return g[k]; } const vector> &operator[](const int &k) const { return g[k]; } void read(int m, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < m; ++i) { int a, b; T c(1); cin >> a >> b; a += padding; b += padding; if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } }; #line 3 "test.cpp" int main() { INT(n, m); Graph g(n); g.read(m); INT(k); vector a(n, false); rep(k) { INT(ai); a[--ai] = true; } vector d(n, vi(5, -1)); queue q; q.push({0, 0}); d[0][0] = 0; while(q.size()) { auto [i, num] = q.front(); q.pop(); for(auto to : g[i]) { int nex = a[to] ? num + 1 : 0; if(nex == 5 or d[to][nex] != -1) continue; d[to][nex] = d[i][num] + 1; q.push({to, nex}); } } int ans = -1; rep(i, 5) { if(ans == -1) ans = d[n - 1][i]; else if(d[n - 1][i] != -1) { chmin(ans, d[n - 1][i]); } } debug(d); print(ans); }