require "set" INF = 1 << 60 N, M = gets.split.map(&:to_i) edges = Array.new(N) { [] } M.times do |i| u, v = gets.split.map(&:to_i).map(&:pred) edges[u] << v edges[v] << u end K = gets.to_i A = K.zero? ? [] : gets.split.map(&:to_i).map(&:pred).to_set dists = Array.new(N) { Array.new(5, INF) } dists[0][0] = 0 # [pos d, danger] log = [[0, 0, 0 ]] until log.empty? pos, d, danger = log.shift if pos == N - 1 puts d exit end next if dists[pos][danger] < d edges[pos].each do |nxt| nd = A.include?(nxt) ? danger + 1 : 0 next if nd >= 5 || dists[nxt][nd] <= d + 1 dists[nxt][nd] = d + 1 log << [nxt, d + 1, nd] end end puts -1