USACO 2026 Third Contest, Gold

Problem 2. Picking Flowers


Contest has ended.

Log in to allow submissions in analysis mode


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

INPUT FORMAT (input arrives from the terminal / stdin):

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.

OUTPUT FORMAT (print output to the terminal / stdout):

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 INPUT:

1
7 7 0 1

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

SAMPLE OUTPUT:

111110
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 INPUT:

1
6 6 0 2

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

SAMPLE OUTPUT:

11010

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 INPUT:

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

SAMPLE OUTPUT:

111
000
1011

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

Contest has ended. No further submissions allowed.