CF2109D D/D/D

_Of 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.

Each 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.

For 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.

In 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 $ \].