Paris Escape

Many of you may know that the Mona Lisa is one of the most famous paintings in the world. One day, Mark decided to steal it. After sneaking into the Louvre, he snatched the painting and escaped into the catacombs of Paris. Unfortunately, security quickly noticed that the Mona Lisa was missing. The police swarmed into the catacombs, but luckily for Mark, they do not know where he is or where he wants to go.

The catacombs consist of rooms connected by corridors, which are tricky to navigate. Mark once looked at a map that labels the $n$ rooms with integers from $0$ to $n-1$. He is in room $0$ now, and the catacombs exit is hidden in room $n-1$. He knows the rooms where all $p$ police officers currently are, so he can make a plan. He must be wary of the police, however. Every minute, each officer walks down a passage chosen uniformly at random from the passages leading out of their current room. Mark cannot sit still either, so he must also take a passage every minute. Passages vary in length, but Mark and the officers traverse each one in exactly one minute.

Mark can attempt to bribe an officer, but he would rather not. Given the map and the starting positions of the police, find the expected number of police encounters during Mark's escape, assuming he moves optimally to minimize it. An encounter happens when Mark and an officer are in the same room at the same time. Passing an officer in the opposite direction in a corridor is not an encounter. If several officers are in the room at the same time, each one counts as a separate encounter. This rule also applies to room $n-1$: if Mark reaches it while an officer occupies it, he is caught before he can escape. Mark may bump into the same officer several times, depending on his path and luck, and each meeting counts. Mark cannot improvise, so once he sets out on a planned path, he cannot change it after meeting officers.

The first line contains two space-separated integers $n$ and $m$, the number of rooms and passages ($2 \le n \le 5 \cdot 10^2$ and $1 \le m \le 5 \cdot 10^3$). Each of the next $m$ lines contains a pair of integers $u$ and $v$ ($0 \le u,v \le n-1$), meaning a bidirectional corridor connects rooms $u$ and $v$. It is guaranteed that $u \ne v$, that no two corridors connect the same pair of rooms, and that every room can be reached from every other room.

The next line contains a single integer $p$, the number of police officers ($0 \le p \le 10$). Each of the next $p$ lines contains a single integer $w$ ($1 \le w \le n-1$), the starting room of one officer. No officer starts in room $0$, where Mark is.

Print the expected number of police encounters for Mark's optimal plan. An answer with an absolute or relative error below $10^{-6}$ is accepted.