← 返回题目列表

Codeforces · 1741/G

G. 基里尔公司

中文机器翻译题面 查看原题

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$$$的朋友必须步行。