/* -*- coding: utf-8 -*- * * 3263.cc: No.3263 驕墓ウ輔↑謨」豁ゥ驕・- yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int C = 5; /* typedef */ using vi = vector; using qi = queue; /* global variables */ vi nbrs[MAX_N]; int fs[MAX_N], ds[MAX_N * C]; /* subroutines */ /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back(v); nbrs[v].push_back(u); } int k; scanf("%d", &k); for (int i = 0; i < k; i++) { int ai; scanf("%d", &ai), ai--; fs[ai] = 1; } fill(ds, ds + n * C, -1); ds[0] = 0; qi q; q.push(0); int gd = -1; while (! q.empty()) { int u = q.front(); q.pop(); int up = u / C, uc = u % C; if (up == n - 1) { gd = ds[u]; break; } for (auto vp: nbrs[up]) { int vc = fs[vp] ? uc + fs[vp] : 0; if (vc < C) { int v = vp * C + vc; if (ds[v] < 0) { ds[v] = ds[u] + 1; q.push(v); } } } } printf("%d\n", gd); return 0; }