CF1741G.Kirill and Company

Kirill lives on a connected undirected graph of $n$ vertices and $m$ edges at vertex $1$. One fine evening he gathered $f$ friends, the $i$-th friend lives at the vertex $h_i$. So all friends are now in the vertex $1$, the $i$-th friend must get to his home to the vertex $h_i$.

The evening is about to end and it is time to leave. It turned out that $k$ ($k \le 6$) of his friends have no cars, and they would have to walk if no one gives them a ride. One friend with a car can give a ride to any number of friends without cars, but only if he can give them a ride by driving along one of the shortest paths to his house.

For example, in the graph below, a friend from vertex $h_i=5$ can give a ride to friends from the following sets of vertices: $[2, 3]$, $[2, 4]$, $[2]$, $[3]$, $[4]$, but can't give a ride to friend from vertex $6$ or a set $[3, 4]$.

The vertices where friends without cars live are highlighted in green, and with cars — in red.

Kirill wants as few friends as possible to have to walk. Help him find the minimum possible number.

基里尔住在一个包含 $n$ 个顶点和 $m$ 条边的连通无向图上，起始位置为顶点 $1$。某天傍晚，他召集了 $f$ 位朋友，其中第 $i$ 位朋友住在顶点 $h_i$。因此，所有朋友当前均位于顶点 $1$，而第 $i$ 位朋友需前往其住所顶点 $h_i$。

夜晚即将结束，是时候离开了。结果发现，他的 $k$（$k \le 6$）位朋友没有车，若无人搭载，他们将不得不步行。一位有车的朋友可以搭载任意数量的无车朋友，但前提是：他必须能沿着一条通往自己家的最短路径，顺路将这些朋友送达各自住所。

例如，在下图中，一位住在顶点 $h_i = 5$ 的朋友可以搭载以下顶点集合中的朋友：$[2, 3]$、$[2, 4]$、$[2]$、$[3]$、$[4]$；但无法搭载住在顶点 $6$ 的朋友，也无法同时搭载住在顶点 $3$ 和 $4$ 的朋友（即集合 $[3, 4]$）。

图中绿色顶点表示无车朋友的住所，红色顶点表示有车朋友的住所。

基里尔希望尽可能少的朋友步行。请帮助他找出最少可能的步行人数。

The first line of input data contains an integer $t$ ($1 \le t \le 10^3$) — the number of test cases in the test.

The first line of the test case contains two integers $n$ and $m$ ($2 \le n \le 10^4$, $n-1 \le m \le min (10^4, $$ \frac{n \cdot (n - 1)}{2} $$)$) — the number of vertices and edges, respectively.

The next $m$ lines of the test case contain a description of the edges, two integers each $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — indexes of vertices connected by an edge. It is guaranteed that there is at most one edge between any pair of vertices (i.e. no multiple edges in the graph).

Then follows line containing the number $f$ ($1 \le f \le 10^4$) — the number of Kirill's friends.

The next line of the test case contains $f$ integers: $h_1, h_2, \dots, h_f$ ($2 \le h_i \le n$) — the vertices in which they live. Some vertices may be repeated.

The next line of the set contains the number $k$ ($1 \le k \le min(6, f)$) — the number of friends without cars.

The last line of each test case contains $k$ integers: $p_1, p_2, \dots, p_k$ ($1 \le p_i \le f$, $p_i \lt p_{i+1}$) — indexes of friends without cars.

It is guaranteed that the sum of $n$ over all cases does not exceed $10^4$, as well as the sums of $m$ and $f$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^4$，$n-1 \le m \le \min\left(10^4, \frac{n \cdot (n - 1)}{2}\right)$）—— 分别表示图的顶点数和边数。

接下来的 $m$ 行描述图中的边，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$）—— 表示由该边连接的两个顶点的编号。保证任意一对顶点之间至多存在一条边（即图中无重边）。

随后一行包含一个整数 $f$（$1 \le f \le 10^4$）—— 表示基里尔的朋友数量。

测试用例的下一行包含 $f$ 个整数：$h_1, h_2, \dots, h_f$（$2 \le h_i \le n$）—— 表示每位朋友所居住的顶点编号。某些顶点可能被重复列出。

接下来一行包含一个整数 $k$（$1 \le k \le \min(6, f)$）—— 表示没有汽车的朋友人数。

每个测试用例的最后一行包含 $k$ 个整数：$p_1, p_2, \dots, p_k$（$1 \le p_i \le f$，且 $p_i < p_{i+1}$）—— 表示没有汽车的朋友在前述 $f$ 人列表中的索引。

保证所有测试用例的 $n$ 之和不超过 $10^4$，同理，所有测试用例的 $m$ 之和与 $f$ 之和也不超过 $10^4$。

Output $t$ lines, each of which contains the answer to the corresponding test case. As an answer, output a single integer — the minimum possible number of friends who will have to walk.

输出 $t$ 行，每行包含对应测试用例的答案。作为答案，输出一个整数——必须步行的朋友的最少人数。

The first test case of the first example is explained in the statement.

In the second test case of the first example, two friends with cars live at vertex $5$, one can give a ride to friends from vertices $2$ and $3$, and the second from vertex $4$, only a friend from vertex $6$ will have to walk.

第一个示例的第一个测试用例已在题面中说明。

在第一个示例的第二个测试用例中，有两位拥有汽车的朋友住在顶点 $5$；其中一位可以顺路搭载来自顶点 $2$ 和 $3$ 的朋友，另一位可以顺路搭载来自顶点 $4$ 的朋友，只有来自顶点 $6$ 的朋友需要步行。