当然,字母 D 的问题是由 Declan Akaba 发起的。
给你一个简单的、连通的、无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。该图不包含自环或多重边。您还会获得一个由 $$$\ell$$$ 元素组成的多重集 $$$A$$$: $$A = \{A_1, A_2, \ldots, A_\ell\}$$
从顶点 $$$1$$$ 开始,您可以执行以下移动 任意号码 次,只要多重集 $$$A$$$ 不为空:
- 选择 A$$$ 中的元素 $$$k 并将其从多重集中删除。您必须从 $$$A$$$ 中删除一次出现的 $$$k$$$。
- 遍历任意 $$$^{\text{∗}}$$$ 的 $$$k$$$ 边,以到达某个顶点(可能与您开始的顶点相同)。
对于每个 $$$i$$$ ($$$1 \le i \le n$$$),使用原始多重集 $$$A$$$ 确定是否存在从顶点 $$$1$$$ 开始并在顶点 $$$i$$$ 结束的此类移动序列。
请注意,对每个顶点 $$$i$$$ 的检查是独立的 - 您从顶点 $$$1$$$ 重新启动,并针对每种情况使用原始多重集 $$$A$$$。
$$$^{\text{*}}$$$长度为 $$$k$$$ 的游走是一系列顶点 $$$v_0, v_1, \ldots, v_{k - 1}, v_k$$$,使得每对连续的顶点 $$$(v_i, v_{i + 1})$$$ 通过图中的边连接。 The sequence may include repeated vertices.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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 \lt v \le n$$$) - 图中边的端点。
保证边形成一个简单的连通图,没有自环或多边。
保证所有测试用例的 $$$n$$$ 之和、$$$m$$$ 之和以及 $$$\ell$$$ 之和分别不超过 $$$2 \cdot 10^5$$$、$$$4 \cdot 10^5$$$ 和 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串,其中如果存在以顶点 $$$i$$$ 结尾的移动序列,则第 $$$i$$$ 个字符为 $$$\mathtt{1}$$$,否则为 $$$\mathtt{0}$$$。
示例
输入复制
36 5 22 31 22 33 44 55 65 5 151 22 33 44 53 55 4 3100 200 3001 21 31 42 5
输出复制
111101 11111 10001
注意
在第一个测试用例中:
- 无需进行任何移动即可到达顶点 $$$1$$$。
- 通过选择 A$$$ 中的元素 $$$3 可以到达顶点 $$$2$$$;一种可能的步行是 [$$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$$$]。
- 通过选择元素 $$$2 \in A$$$ 并步行 [$$$1 \rightarrow 2 \rightarrow 3$$$] 可以到达顶点 $$$3$$$。
- 通过选择元素 $$$3 \in A$$$ 并遵循步行 [$$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$] 可以到达顶点 $$$4$$$。
- 任何有效的移动序列都无法到达顶点 $$$5$$$。
- 通过首先选择元素 $$$2 \in A$$$ 并进行步行 [$$$1 \rightarrow 2 \rightarrow 3$$$],然后选择元素 $$$3 \in A$$$ 并进行步行 [$$$3 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$],可以到达顶点 $$$6$$$。