题目描述

SPY 喜欢有用的算法，而 Markyyz 总是学习无用的算法。尽管他们学习的算法类型不同，但他们都喜欢一款名为 Counter Strike（简称“CS”，与现实中的同名游戏不同）的电脑游戏。这是一个双人竞技游戏。一名玩家扮演恐怖分子（简称“T”），负责安放炸弹。另一名玩家扮演反恐精英（简称“CT”），负责拆除炸弹。

每局游戏开始时，系统会生成一个带有电路的炸弹。该电路由 $n$ 个集线器（编号从 $1$ 到 $n$）和 $m$ 根导线组成。每根导线连接两个不同的集线器，任意两个集线器之间可以通过导线直接或间接相连，且没有两个集线器之间被多于一根导线直接连接。换句话说，该电路可以被视为一个具有 $n$ 个顶点和 $m$ 条边的无向图，没有重边和自环。

游戏分为三个阶段：

1. 安放炸弹阶段：$T$ 将获得 $k$ 个编号为 $1$ 到 $k$ 的启动组件。$T$ 需要选择 $k$ 个不同的集线器 $h_1, h_2, \ldots , h_k$，并将第 $i$ 个启动组件安放在第 $h_i$ 号集线器上。
2. 拆除炸弹阶段：$CT$ 将免费获得一个有用的工具包，并购买 $q$ 个编号为 $1$ 到 $q$ 的无用工具包。有用的工具包可以移除任意一个集线器，而无用的工具包只能按顺序移除带有启动组件的集线器，这意味着第 $i$ 个无用工具包只能移除第 $h_i$ 号集线器。一旦一个集线器被移除，所有与其直接相连的导线都将被切断。
3. 炸弹激活阶段：如果任意两个启动组件之间通过导线直接或间接相连，则炸弹将被激活，$T$ 获胜。否则，炸弹将被拆除，$CT$ 获胜。

例如，上图展示了一个炸弹电路，由 $19$ 个集线器和 $27$ 根导线组成。$T$ 获得了 $6$ 个启动组件，并将它们安放在 $16, 17, 2, 18, 12, 9$ 号集线器上。$CT$ 可以购买 $2$ 个无用工具包。

现在，Markyyz 扮演 $T$，SPY 扮演 $CT$。Markyyz 已经放置好了 $k$ 个启动组件。为了在未来的游戏中省钱，SPY 希望购买最少数量的无用工具包来拆除炸弹。尽管 SPY 自认为是实用算法大师，但他无法在 $O((n + m)\log n)$ 的时间复杂度内找到答案。你能帮他计算出答案吗（换句话说，就是 $CT$ 获胜所需的最小 $q$ 值）？

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。

对于每个测试用例：

第一行包含三个整数 $n, m, k$（$2 \leq n, m \leq 2 \times 10^{5}, 2 \leq k \leq n$），分别表示集线器（顶点）的数量、导线（边）的数量和启动组件的数量。

接下来的 $m$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq n, u \neq v$），表示连接第 $u$ 号集线器和第 $v$ 号集线器的一根导线。

下一行包含 $k$ 个不同的整数 $h_{1}, h_{2}, \ldots , h_{k}$（$1 \leq h_{i} \leq n$）。第 $i$ 个启动组件被安放在第 $h_i$ 号集线器上。

保证所有测试用例的 $\sum n, \sum m \leq 10^{6}$。

输出格式

每个测试用例输出一行一个整数，表示 $CT$ 获胜所需的最小 $q$ 值。

1
19 27 6
1 2
1 3
1 4
2 4
3 4
2 5
4 5
5 6
5 8
6 7
6 8
8 7
8 9
7 9
7 10
9 10
5 11
11 12
12 13
13 14
14 12
11 15
11 16
16 17
16 18
17 18
17 19
18 19
16 17 2 18 12 9

2