说明

注意：本题的时间限制为 3 秒，是默认时间的 1.5 倍。

农夫约翰的农场结构可以表示为一个有 $N$ 个顶点和 $M$ 条无权重边的连通无向图（$2 \leq N \leq 2 \cdot 10^5$，$N - 1 \leq M \leq 2 \cdot 10^5$）。初始时，农夫约翰在他的谷仓，即农场 $1$。

初始时，农场 $s_1, s_2, \ldots, s_K$ 包含花田，而农场 $d_1, d_2, \ldots, d_L$ 是目标农场。FJ 称一条路径为 美丽的，如果它满足：

• 起点是农场 $1$。
• 终点是某个目标农场 $x$。
• 不存在从农场 $1$ 到农场 $x$ 的更短路径。
• FJ 沿途访问了所有花田。

FJ 可以挥动他的魔杖，使得最多再有一个农场（如果原本没有）变成花田。然而，FJ 并不是很果断。对于编号从 $2$ 到 $N$ 的农场 $f$，在 FJ 临时让农场 $f$ 变成花田后，判断是否存在一条美丽的路径。

注意，有多个测试用例，每个用例需独立处理。

输入格式

第一行包含 $T$（$1 \leq T \leq 100$），表示独立测试用例的数量。

每个测试用例的第一行包含 $N$、$M$、$K$ 和 $L$（$0 \leq K \leq N - 1$，$1 \leq L \leq N - 1$）。

接下来的一行包含 $s_1, s_2, \ldots, s_K$（$2 \leq s_i \leq N$，所有 $s_i$ 互不相同）。

接下来的一行包含 $d_1, d_2, \ldots, d_L$（$2 \leq d_i \leq N$，所有 $d_i$ 互不相同）。

接下来的 $M$ 行每行包含 $u$ 和 $v$，表示农场 $u$ 和 $v$ 之间有一条无向边。所有边的长度视为相等。保证没有重边或自环。

保证所有测试用例的 $N$ 之和以及 $M$ 之和均不超过 $10^6$。

输出格式

对于每个测试用例，输出一个长度为 $N - 1$ 的二进制字符串。字符串的第 $i$ 个字符应为 $1$，如果对于第 $i+1$ 号农场的答案为真（即存在美丽路径）。

1
7 7 0 1

5
1 2
2 3
3 4
4 5
5 6
6 7
3 6

111110

1
6 6 0 2

5 3
1 2
2 3
3 4
4 5
5 6
2 5

11010

3
4 3 2 1
2 3
4
1 2
2 3
3 4
4 4 2 1
2 3
4
1 2
1 3
2 4
3 4
5 5 2 1
2 4
5
1 2
1 3
2 4
3 4
4 5

111
000
1011

提示

样例 1 解释

由于 $5$ 是唯一的目标农场，如果第 $i$ 号农场位于从 $1$ 到 $5$ 的任意一条最短路径上，则答案为真。 从 $1$ 到 $5$ 有两条最短路径，分别是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 和 $1 \rightarrow 2 \rightarrow 3 \rightarrow 6 \rightarrow 5$。 由于原本没有农场包含花田，因此对于农场 $i$，如果它位于上述两条路径中的至少一条上，则答案为真。

样例 2 解释

有两个目标农场：$5$ 和 $3$。由于原本没有农场包含花田，第 $i$ 号农场必须位于到 $5$ 或 $3$ 的最短路径上。因为农场 $2$ 位于到农场 $5$ 的一条最短路径上，所以对于农场 $2$ 答案为真。显然，农场 $3$ 位于到农场 $3$ 的最短路径上，农场 $5$ 位于到农场 $5$ 的最短路径上。

样例 3 解释

对于第一个测试用例，如果 FJ 能在某条到农场 $4$ 的最短路径上依次经过农场 $i$、农场 $2$ 和农场 $3$（顺序不限），则对于第 $i$ 号农场答案为真。可以证明，对于所有农场答案均为真。

评分标准

• 输入 4-6：$K = 0$ 且 $L = 1$
• 输入 7-9：$K = 0$
• 输入 10-23：无额外限制

题目来源：Chongtian Ma

翻译由 DeepSeek 完成