2097 - デイリーミッション

問題

PCK君が最近はまっているゲームには毎日更新されるミッションがあり、ミッションを達成すると報酬がもらえる。今日のミッションは、迷宮にいる小鬼を決められた順番にしたがって倒していくというものである。

迷宮の地図には、$1$から$N$までの番号が付いた$N$個の部屋と、部屋と部屋を直接つなぐ$M$本の廊下が記されている。２つの部屋$u$と$v$が廊下で繋がっているとき、その廊下を通って$u$から$v$にも、$v$から$u$にも行くことができる。いくつかの廊下を通ることで、地図上のどの２つの部屋の間も行き来できる。

地図には、倒すべき$K$匹の小鬼がいる部屋番号の列が記されている。$i$番目に倒すべき小鬼がいる部屋番号は列の$i$番目に記される。今日のミッションでは、プレイヤーは列に記された順番に小鬼を1匹ずつ倒すことが求められている。プレイヤーは、自分と同じ部屋にいる小鬼を倒すことができる。この迷宮では、i番目の小鬼を倒すと列に記された次の小鬼が出現するようになっている。ただし、列の1番目に記された小鬼は、ミッション開始時に出現する。ミッション開始時にプレイヤーは部屋1におり、廊下を通って部屋を移動する。移動の際、プレイヤーはどの部屋を何度訪れてもよい。

地図には、毒が漂う部屋番号も記されている。部屋１から出発して部屋を移動しながら、列に記された順番で小鬼を倒すことができる経路はいくつかあり得る。毒が漂う部屋にいる回数が最少になるような経路で迷宮を巡って、すべての小鬼を倒すべき順に倒したときだけ、ミッション達成と認められる。

ミッション達成で得られる報酬は、移動のために通る廊下の数が少ないほど高くなる。PCK君は、得られる報酬を最大にするために、通る廊下の数を最少にしてミッションを達成したい。

迷宮の情報が与えられたとき、ミッション達成までに通る廊下の数の最小値を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$:$
$u_M$ $v_M$
$K$
$a_1$ $a_2$ ... $a_K$
$Q$
$b_1$ $b_2$ ... $b_Q$

１行目に部屋の数$N$ ($2 \leq N \leq 300$)と廊下の数$M$ ($N-1 \leq M \leq N(N-1)/2$)が与えられる。続く$M$行に、$i$番目の廊下によって直接つながる部屋$u_i$と$v_i$ ($1 \leq u_i < v_i \leq N$)が与えられる。ただし、$i \ne j$のとき$u_i \ne u_j$または$v_i \ne v_j$である。続く１行に小鬼の数$K$ ($1 \leq K \leq 200,000=2\times10^5$)が与えられる。続く１行に、小鬼を倒す順番を表す部屋番号の列が与えられる。$i$番目に倒す小鬼のいる部屋は$a_i$ ($1 \leq a_i \leq N$)である。ただし、列の中には同じ部屋番号が続けて現れることはない（すなわち、$a_i \ne a_(i+1)$）ものとする。続く１行に毒が漂う部屋の数$Q$($1 \leq Q \leq N$)が与えられる。続く１行に、毒が漂う部屋$b_i$ ($1 \leq b_i \leq N$)が与えられる。ただし、$i \ne j$のとき$b_i \ne b_j$である。

出力

ミッション達成までに通る廊下の数の最小値を１行に出力する。

入出力例

入力例１

6 7
1 2
1 3
1 6
2 3
3 4
4 5
5 6
3
2 3 6
1
1

出力例１

5

部屋１から出発して１→２→３→４→５→６のように移動することで、部屋２，３，６にいる小鬼を順番に倒せる。１→２→３→１→６のように移動すると通る廊下の数を１つ少なくできるが、毒の漂う部屋１に２回いなければならないのでミッション達成とは認められない。

入力例２

3 2
1 2
2 3
3
3 2 3
2
2 3

出力例２

4

部屋１から出発して１→２→３→２→３のように移動することで、部屋３，２，３にいる小鬼を順番に倒せる。ただし、最初に部屋２を訪れたときは小鬼を倒さない。この経路で移動すると毒の漂う部屋２，３にいる回数は全部で４回になるが、倒すべき順で小鬼を倒すためにはこれ以上回数を少なくすることはできない。