파리 탈출

여러분도 알겠지만 모나리자는 세계에서 가장 유명한 그림 중 하나이다. 어느 날 마크는 이 그림을 훔치기로 했다. 루브르에 몰래 들어가 그림을 낚아챈 뒤 파리의 지하 묘지(카타콤)로 도망쳤다. 안타깝게도 경비 측은 모나리자가 없어진 것을 곧 알아챘다. 경찰이 카타콤으로 몰려들었지만, 다행히 경찰은 마크가 어디에 있는지, 어디로 가려는지 알지 못한다.

카타콤은 복도로 연결된 여러 방으로 이루어져 있어 길을 찾기가 까다롭다. 마크는 전에 본 지도에서 $0$부터 $n-1$까지 번호가 붙은 $n$개의 방을 알고 있다. 마크는 지금 $0$번 방에 있고, 카타콤의 출구는 $n-1$번 방에 숨겨져 있다. 현재 $p$명의 경찰이 각각 어느 방에 있는지도 알고 있으니, 이 정보로 계획을 세울 수 있다. 다만 경찰을 경계해야 한다. 경찰은 매 분마다 현재 방에서 나가는 통로 중 하나를 균등한 확률로 골라 인접한 방으로 걸어간다. 마크도 가만히 있지 못하니 매 분마다 통로를 골라 이동해야 한다. 통로마다 길이는 다르지만, 마크와 경찰은 모든 통로를 정확히 1분에 지난다.

마크는 경찰 한 명에게 뇌물을 줄 수 있지만, 그러고 싶지는 않다. 지도와 경찰의 초기 위치가 주어졌을 때, 마크가 최적으로 움직여 탈출하는 동안 겪는 경찰 조우 횟수의 기댓값을 구하라. 조우는 마크와 경찰이 같은 시각에 같은 방에 있을 때 일어난다. 통로에서 반대 방향으로 가는 경찰과 엇갈리는 것은 조우가 아니다. 같은 시각에 한 방에 경찰이 여럿 있으면, 경찰 한 명마다 따로 조우로 센다. 이 규칙은 $n-1$번 방에도 똑같이 적용된다. 마크가 $n-1$번 방에 도착했을 때 경찰이 그 방에 있으면, 마크는 탈출하기 전에 잡힌다. 마크는 경로와 운에 따라 같은 경찰과 여러 번 마주칠 수 있으며, 마주칠 때마다 조우로 센다. 마크는 상황에 맞게 즉흥적으로 움직일 수 없으므로, 한번 출발한 계획 경로는 경찰과 마주쳐도 바꿀 수 없다.

첫 줄에 방의 수 $n$과 통로의 수 $m$이 공백으로 구분되어 주어진다 ($2 \le n \le 5 \cdot 10^2$, $1 \le m \le 5 \cdot 10^3$). 이어지는 $m$개의 줄에는 두 방 $u$, $v$를 잇는 양방향 복도가 공백으로 구분되어 주어진다 ($0 \le u,v \le n-1$). $u \ne v$이고, 같은 두 방을 잇는 복도는 두 개 이상 없다. 모든 방은 복도를 따라 서로 도달할 수 있다.

다음 줄에는 경찰의 수 $p$가 주어진다 ($0 \le p \le 10$). 이어지는 $p$개의 줄에는 경찰 한 명의 시작 방 $w$가 하나씩 주어진다 ($1 \le w \le n-1$). 마크가 있는 $0$번 방에서 출발하는 경찰은 없다.

마크가 최적으로 움직일 때의 경찰 조우 횟수 기댓값을 하나의 수로 출력하라. 절대 오차 또는 상대 오차가 $10^{-6}$ 미만이면 정답으로 인정한다.