use proconio::input; use std::collections::{HashSet, VecDeque}; fn main() { input! { n: usize, m: usize, } let mut graph = vec![HashSet::::new(); n+1]; for _ in 0..m { input!{ u: usize, v: usize } graph[u].insert(v); graph[v].insert(u); } input!{ k: usize } let mut iwai = vec![false; n+1]; for _ in 0..k { input!{ a: usize } iwai[a] = true; } let mut q = VecDeque::new(); q.push_back((1,0,0)); let mut visited = vec![vec![false; n+1]; 5]; while let Some(state) = q.pop_front() { let (pos, encount, depth) = state; if pos == n { println!("{}", depth); return;} for v in &graph[pos]{ let mut nenc=encount; if iwai[pos] { nenc += 1;} else { nenc = 0; } if nenc == 5 {continue;} if visited[nenc][*v] {continue;} visited[nenc][*v] = true; q.push_back((*v,nenc,depth+1)); } } println!("-1"); }