Kirill 生活在一个由 $$$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]$$$。
没有汽车的朋友居住的顶点以绿色突出显示,有汽车的朋友居住的顶点以红色突出显示。
基里尔希望尽可能少的朋友必须步行。帮助他找到尽可能少的数字。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试中的测试用例数量。
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^4$$$, $$$n-1 \le m \le min (10^4, $$$$$$ \frac{n \cdot (n - 1)}{2} $$$$$$)$$$) — 顶点数和分别为边缘。
测试用例的接下来的 $$$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}$$$) — 没有汽车的朋友的索引。
保证所有情况下$$$n$$$的总和不超过$$$10^4$$$,以及$$$m$$$和$$$f$$$的总和。
输出
输出 $$$t$$$ 行,每行包含相应测试用例的答案。作为答案,输出一个整数——必须步行的最少可能朋友数量。
示例
输入 #1
3 6 7 1 2 2 3 2 4 3 5 4 5 3 6 6 5 5 2 3 4 5 6 4 1 2 3 5 6 7 1 2 2 3 2 4 3 5 4 5 3 6 6 5 6 2 3 4 5 6 5 4 1 2 3 5 4 4 1 2 1 3 2 3 3 4 3 3 4 2 2 1 3
输出 #1
2 1 1
输入 #2
3 2 1 1 2 3 2 2 2 3 1 2 3 3 3 1 2 1 3 2 3 4 2 2 2 3 3 1 2 4 4 4 3 1 3 2 1 4 2 4 5 3 2 2 4 2 3 1 3 4
输出 #2
3 1 0
注意
语句中解释了第一个示例的第一个测试用例。
在第一个示例的第二个测试用例中,两个有汽车的朋友住在顶点$$$5$$$,一个可以搭车来自顶点$$$2$$$和$$$3$$$的朋友,第二个来自顶点$$$4$$$,只有来自顶点$$$6$$$的朋友必须步行。