P15577 [USACO26FEB] Picking Flowers G

**Note: The time limit for this problem is 3s, 1.5x the default.** Farmer John's farm structure can be represented as a connected undirected graph with $N$ vertices and $M$ unweighted edges ($2 \leq N \leq 2 \cdot 10^5, N - 1 \leq M \leq 2 \cdot 10^5$). Initially, Farmer John is at his barn, represented by farm $1$. Initially, farms $s_1, s_2, \ldots, s_K$ contain flower fields and farms $d_1, d_2, \ldots, d_L$ are destination farms. FJ calls a path pretty if: - It starts at farm $1$. - It ends at some destination farm $x$. - There is no shorter path starting at farm $1$ and ending at farm $x$. - FJ visits all flower fields along the way. FJ can wave his magic wand and make up to one more farm contain a flower field (if it doesn't already). However, FJ isn't very decisive. For farms $f$ numbered $2$ through $N$, after FJ temporarily makes farm $f$ contain a flower field, determine if there exists a pretty path. Note that there are multiple test cases, and each case must be treated independently.

The first line contains $T$ ($1 \leq T \leq 100$), the number of independent test cases. The first line of each test case contains $N$, $M$, $K$, and $L$ ($0 \leq K \leq N - 1, 1 \leq L \leq N - 1$). The following line contains $s_1, s_2, \ldots, s_K$ ($2 \leq s_i \leq N$, $s_i$ are all distinct). The following line contains $d_1, d_2, \ldots, d_L$ ($2 \leq d_i \leq N$, $d_i$ are all distinct). The following $M$ lines contain $u$ and $v$, denoting there is an undirected edge between farms $u$ and $v$. All edges are considered to have equal length. It is guaranteed that there aren't any multi-edges or self loops. It is guaranteed that both the sum of $N$ and the sum of $M$ do not exceed $10^6$ over all test cases.

For each test case, output a binary string of length $N - 1$. The $i$'th character in the string should be $1$ if the answer holds true for the $(i+1)$'th farm.

### Sample 1 Explanation Since $5$ is the only destination farm, the answer holds true if the $i$'th farm lies on any shortest path from $1$ to $5$. There are two shortest paths from $1$ to $5$, which are $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ and $1 \rightarrow 2 \rightarrow 3 \rightarrow 6 \rightarrow 5$. Since there are no farms that already contain flower fields, the answer for farm $i$ holds true if farm $i$ lies on at least one of the two aforementioned paths. ### Sample 2 Explanation There are two destination farms: $5$ and $3$. Since there are no farms that already contain flower fields, the $i$'th farm must lie on a shortest path to either $5$ or $3$. Since farm $2$ lies on a shortest path to farm $5$, so the answer holds for farm $2$. Trivially, farm $3$ lies on the shortest path to farm $3$ and farm $5$ lies on the shortest path to farm $5$. ### Sample 3 Explanation For the first test case, the answer holds true for the $i$'th farm if FJ can pass through farm $i$, farm $2$, and farm $3$ (in no particular order) on some shortest path to farm $4$. It can be shown that the answer holds true for all farms. ### SCORING: - Inputs 4-6: $K = 0$ and $L = 1$ - Inputs 7-9: $K = 0$ - Inputs 10-23: No additional constraints Problem credits: Chongtian Ma