题目描述

给你一个简单、连通的无向图，图中有 $n$ 个顶点和 $m$ 条边。该图不包含自循环或多条边。同时给你一个由 $\ell$ 个元素组成的多集合 $A$ ：

从顶点 $1$ 开始，只要多集合 $A$ 不为空，您就可以执行下面的移动 ** 次数**：

• 选择元素 $k \in A$ 并将其从多集合中移除。您必须从 $A$ 中移除 $k$ 中的一个元素。
• 遍历由恰好 $k$ 条边组成的任意行走 $^{\text{∗}}$ ，到达某个顶点（可能是从同一个顶点开始的）。

对于每个 $i$ ( $1 \le i \le n$ )，使用原始的多集合 $A$ 判断是否存在一个从顶点 $1$ 开始到顶点 $i$ 结束的移动序列。

请注意，对每个顶点 $i$ 的检查都是独立的 - 我们从顶点 $1$ 重新开始，并在每种情况下使用原始多集合 $A$ 。

{长度为 $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 \lt v \le n$ ) --图中一条边的端点。

保证这些边构成了一个简单的连通图，没有自循环或多条边。

保证所有测试用例的 $n$ 、 $m$ 和 $\ell$ 之和分别不超过 $2 \cdot 10^5$ 、 $4 \cdot 10^5$ 和 $2 \cdot 10^5$ 。

输出格式

输出

对于每个测试用例，输出长度为 $n$ 的二进制字符串，其中如果存在以顶点 $i$ 为终点的移动序列， $i$ /-th 字符为 $\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$ 无需移动即可到达。
• 选择元素 $3 \in A$ 可以到达顶点 $2$ ；一种可能的走法是 [ $1 \rightarrow 2 \rightarrow 1 \rightarrow 2$ ]。
• 顶点 $3$ 可以通过选择元素 $2 \in A$ 并走[ $1 \rightarrow 2 \rightarrow 3$ ]到达。
• 选择元素 $3 \in A$ 并沿着 [ $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ]走可以到达顶点 $4$ .
• 任何有效的移动序列都无法到达顶点 $5$ 。
• 顶点 $6$ 可以通过先选择元素 $2 \in A$ 并走 [ $1 \rightarrow 2 \rightarrow 3$ ]，然后选择元素 $3 \in A$ 并走 [ $3 \rightarrow 4 \rightarrow 5 \rightarrow 6$ ]到达。