#include using namespace std; void bfs(const vector>& graph, vector& distances, const int& start) { deque que; que.push_back(start); distances.at(start) = 0; while (!que.empty()) { for (int vertex : graph.at(que.front())) { if (distances.at(vertex)==-1) { distances.at(vertex) = distances.at(que.front())+1; que.push_back(vertex); } } que.pop_front(); } } /////////////////// メイン /////////////////// int main () { //////////////////// 入力 //////////////////// int n, m; cin >> n >> m; vector u(m), v(m); for (int i=0; i> u.at(i) >> v.at(i); u.at(i)--; v.at(i)--; } int k; cin >> k; vector flags(n,false); for (int i=0; i> a; a--; flags.at(a) = true; } //////////////// 出力変数定義 //////////////// int result = 0; //////////////////// 処理 //////////////////// vector> graph(5*n); for (int i=0; i> p = {{u.at(i),v.at(i)},{v.at(i),u.at(i)}}; for (auto [v1,v2] : p) { if (flags.at(v2)) { graph.at(v1).emplace_back(v2+n); graph.at(v1+n).emplace_back(v2+2*n); graph.at(v1+2*n).emplace_back(v2+3*n); graph.at(v1+3*n).emplace_back(v2+4*n); } else { graph.at(v1).emplace_back(v2); graph.at(v1+n).emplace_back(v2); graph.at(v1+2*n).emplace_back(v2); graph.at(v1+3*n).emplace_back(v2); graph.at(v1+4*n).emplace_back(v2); } } } vector distances(5*n,-1); bfs(graph,distances,0); result = distances.at(n-1); //////////////////// 出力 //////////////////// cout << result << endl; //////////////////// 終了 //////////////////// return 0; }