D. D/D/Dtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputOf course, a problem with the letter D is sponsored by Declan Akaba.You are given a simple, connected, undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The graph contains no self-loops or multiple edges. You are also given a multiset $$$A$$$ consisting of $$$\ell$$$ elements: $$$$$$ A = \{A_1, A_2, \ldots, A_\ell\} $$$$$$Starting from vertex $$$1$$$, you may perform the following move any number of times, as long as the multiset $$$A$$$ is not empty: Select an element $$$k \in A$$$ and remove it from the multiset . You must remove exactly one occurrence of $$$k$$$ from $$$A$$$. Traverse any walk$$$^{\text{∗}}$$$ of exactly $$$k$$$ edges to reach some vertex (possibly the same one you started from). For each $$$i$$$ ($$$1 \le i \le n$$$), determine whether there exists a sequence of such moves that starts at vertex $$$1$$$ and ends at vertex $$$i$$$, using the original multiset $$$A$$$. Note that the check for each vertex $$$i$$$ is independent — you restart from vertex $$$1$$$ and use the original multiset $$$A$$$ for each case.$$$^{\text{∗}}$$$A walk of length $$$k$$$ is a sequence of vertices $$$v_0, v_1, \ldots, v_{k - 1}, v_k$$$ such that each consecutive pair of vertices $$$(v_i, v_{i + 1})$$$ is connected by an edge in the graph. The sequence may include repeated vertices.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$\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$$$) — the number of vertices, the number of edges, and the size of the multiset, respectively.The second line of each test case contains $$$\ell$$$ integers $$$A_1, A_2, \ldots, A_{\ell}$$$ ($$$1 \leq A_i \leq 10^4$$$) — the elements of the multiset.Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u < v \le n$$$) — the endpoints of an edge in the graph. It is guaranteed that the edges form a simple, connected graph without self-loops or multiple edges.It is guaranteed that the sum of $$$n$$$, the sum of $$$m$$$, and the sum of $$$\ell$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, $$$4 \cdot 10^5$$$, and $$$2 \cdot 10^5$$$, respectively.OutputFor each test case, output a binary string of length $$$n$$$, where the $$$i$$$-th character is $$$\mathtt{1}$$$ if there exists a sequence of moves ending at vertex $$$i$$$, and $$$\mathtt{0}$$$ otherwise.ExampleInput36 5 22 31 22 33 44 55 65 5 151 22 33 44 53 55 4 3100 200 3001 21 31 42 5Output111101
11111
10001
NoteIn the first test case: Vertex $$$1$$$ is reachable without making any moves. Vertex $$$2$$$ is reachable by selecting element $$$3 \in A$$$; one possible walk is [$$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$$$]. Vertex $$$3$$$ can be reached by selecting element $$$2 \in A$$$ and taking the walk [$$$1 \rightarrow 2 \rightarrow 3$$$]. Vertex $$$4$$$ is reachable by selecting element $$$3 \in A$$$ and following the walk [$$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$]. Vertex $$$5$$$ is not reachable by any valid sequence of moves. Vertex $$$6$$$ is reachable by first selecting element $$$2 \in A$$$ and taking the walk [$$$1 \rightarrow 2 \rightarrow 3$$$], followed by selecting element $$$3 \in A$$$ and taking the walk [$$$3 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$].