← 返回题目列表

Codeforces · 2109/D

D. D/D/D问题

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

当然,字母 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}$$$。

示例

输入
复制

3
6 5 2
2 3
1 2
2 3
3 4
4 5
5 6
5 5 1
5
1 2
2 3
3 4
4 5
3 5
5 4 3
100 200 300
1 2
1 3
1 4
2 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$$$。