#include using namespace std; using ll = long long; int main(){ int n,m; cin >> n >> m; vector>path (n,vector(0)); for(int i=0;i> x >> y; x--,y--; path[x].push_back(y); path[y].push_back(x); } vectoriwi (n,0); int k; cin >> k; for(int i=0;i> x; iwi[x-1] = 1; } int inf = (1<<30); vector>dp (5,vector(n,inf)); dp[0][0] = 0; queue>>que; que.push({0,{0,0}}); while(!que.empty()){ auto [stp,hoge] = que.front(); auto [app,pos] = hoge; que.pop(); if(stp > dp[app][pos]) continue; for(auto nex:path[pos]){ int np; if(iwi[nex] == 0) np = 0; else np = app + 1; if(np == 5) continue; if(dp[np][nex] > dp[app][pos] + 1){ dp[np][nex] = dp[app][pos] + 1; que.push({dp[np][nex],{np,nex}}); } } } int cnt = inf; for(int i=0;i<5;i++){ cnt = min(cnt,dp[i][n-1]); } if(cnt == inf) cout << "-1" << endl; else cout << cnt << endl; }