CF2109D D/D/D

当然，这道以字母 D 开头的题目是由 Declan Akaba 赞助的。 给定一个简单、连通的无向图，包含 $n$ 个顶点和 $m$ 条边。图中没有自环或重边。同时给定一个包含 $\ell$ 个元素的多重集 $A$： $$ A = \{A_1, A_2, \ldots, A_\ell\} $$ 从顶点 $1$ 出发，你可以执行以下操作任意次数（只要多重集 $A$ 不为空）： - 从多重集 $A$ 中选择一个元素 $k$ 并移除它（必须移除 $k$ 的一个实例）。 - 遍历恰好包含 $k$ 条边的任意路径$^{\text{∗}}$，到达某个顶点（可以是起始顶点本身）。 对于每个 $i$（$1 \le i \le n$），判断是否存在一个操作序列，使得从顶点 $1$ 出发，使用原始多重集 $A$，最终能到达顶点 $i$。 注意：对每个顶点 $i$ 的检查是独立的——每次都需要从顶点 $1$ 重新开始，并使用原始多重集 $A$。 $^{\text{∗}}$ 长度为 $k$ 的路径是指一个顶点序列 $v_0, v_1, \ldots, v_{k-1}, v_k$，其中每对相邻顶点 $(v_i, v_{i+1})$ 都由图中的一条边连接。序列中允许包含重复的顶点。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $\ell$（$2 \leq n \leq 2 \cdot 10^5$，$n-1 \leq m \leq 4 \cdot 10^5$，$1 \leq \ell \leq 2 \cdot 10^5$）——分别表示顶点数、边数和多重集的大小。 第二行包含 $\ell$ 个整数 $A_1, A_2, \ldots, A_{\ell}$（$1 \leq A_i \leq 10^4$）——多重集的元素。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u < v \le n$）——表示图中的一条边。 保证边构成一个简单、连通的无向图，没有自环或重边。 保证所有测试用例的 $n$ 之和、$m$ 之和以及 $\ell$ 之和分别不超过 $2 \cdot 10^5$、$4 \cdot 10^5$ 和 $2 \cdot 10^5$。

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串，其中第 $i$ 个字符为 $\mathtt{1}$ 表示存在到达顶点 $i$ 的操作序列，否则为 $\mathtt{0}$。

**第一个测试用例解释：** - 顶点 $1$ 无需任何操作即可到达。 - 顶点 $2$ 可通过选择 $A$ 中的元素 $3$ 到达，例如路径 $[1 \rightarrow 2 \rightarrow 1 \rightarrow 2]$。 - 顶点 $3$ 可通过选择 $A$ 中的元素 $2$ 并走路径 $[1 \rightarrow 2 \rightarrow 3]$ 到达。 - 顶点 $4$ 可通过选择 $A$ 中的元素 $3$ 并走路径 $[1 \rightarrow 2 \rightarrow 3 \rightarrow 4]$ 到达。 - 顶点 $5$ 无法通过任何有效操作序列到达。 - 顶点 $6$ 可通过以下方式到达： 1. 选择 $A$ 中的元素 $2$ 并走路径 $[1 \rightarrow 2 \rightarrow 3]$； 2. 选择 $A$ 中的元素 $3$ 并走路径 $[3 \rightarrow 4 \rightarrow 5 \rightarrow 6]$。 翻译由 DeepSeek V3 完成