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

Farmer John 的农场结构可以表示为一个包含 $N$ 个顶点和 $M$ 条无权边的连通无向图（$2 \leq N \leq 2 \cdot 10^5, N - 1 \leq M \leq 2 \cdot 10^5$）。最初，Farmer John 位于他的谷仓，即农场 $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$，否则为 $0$。

样例

样例输入 1

1
7 7 0 1

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

样例输出 1

111110

说明 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

1
6 6 0 2

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

样例输出 2

11010

说明 2

有两个目标农场：$5$ 和 $3$。由于目前没有任何农场包含花田，第 $i$ 个农场必须位于通往 $5$ 或 $3$ 的某条最短路径上。由于农场 $2$ 位于通往农场 $5$ 的最短路径上，因此农场 $2$ 的答案成立。显然，农场 $3$ 位于通往农场 $3$ 的最短路径上，农场 $5$ 位于通往农场 $5$ 的最短路径上。

样例输入 3

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

样例输出 3

111
000
1011

说明 3

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

子任务

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