AT_jsc2026_final_b Binary Flood

有一个包含 $N$ 个顶点 $M$ 条边的连通简单无向二分图 $G$。顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。 初始时，每个顶点被染为黑色或白色，顶点 $1$ 为黑色。此外，每条边相连的两个顶点颜色不同。由此可知所有顶点的颜色是唯一确定的。 你可以进行任意次如下操作： - 从 $A_1,A_2,\ldots,A_K$ 这 $K$ 个顶点中选择一个，设为 $v$。在 $G$ 中，以 $v$ 所在的同色顶点组成的诱导子图里，将与 $v$ 连通的所有顶点的颜色反转（黑变白，白变黑）。 请你求出，为了让所有顶点颜色相同，最少需要操作多少次。 你需要对 $T$ 个测试用例分别求解并输出答案。 诱导子图指的是，若 $S$ 是 $G$ 的顶点的一个子集，则由 $S$ 构成的诱导子图是指顶点集合为 $S$，边集合为“两端都在 $S$ 内的 $G$ 的边” 的图。

输入按以下格式从标准输入读入。 > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每个测试用例按以下格式给出： > $N$ $M$ $K$ > $A_1$ $A_2$ $\ldots$ $A_K$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$

输出 $T$ 行。 第 $i$ 行输出第 $i$ 个测试用例的答案。

### 样例解释 1 在第 $1$ 个测试用例中，初始时顶点 $1,4$ 为黑色，顶点 $2,3,5$ 为白色。按照如下步骤进行操作，只需 $2$ 次即可让所有顶点颜色相同。 - 选择顶点 $3$，顶点 $3$ 的颜色变为黑色。 - 选择顶点 $1$，顶点 $1,3,4$ 的颜色变为白色。 ### 数据范围 - $1 \le T \le 10^4$ - $2 \le N \le 2 \times 10^5$ - $N-1 \le M \le 2 \times 10^5$ - $1 \le K \le \min(N, 10)$ - $1 \le A_1 < A_2 < \ldots < A_K \le N$ - $1 \le U_i < V_i \le N$ - $G$ 为连通的简单无向二分图 - 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$ - 所有测试用例中 $M$ 的总和不超过 $2 \times 10^5$ - 输入数据均为整数。 由 ChatGPT 5 翻译