#215522. [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 vertices and unweighted edges (). Initially, Farmer John is at his barn, represented by farm .

Initially, farms contain flower fields and farms are destination farms. FJ calls a path pretty if:

• It starts at farm .
• It ends at some destination farm .
• There is no shorter path starting at farm and ending at farm .
• 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 numbered through , after FJ temporarily makes farm 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 (), the number of independent test cases. The first line of each test case contains , , , and ().

The following line contains (, are all distinct).

The following line contains (, are all distinct).

The following lines contain and , denoting there is an undirected edge between farms and . 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 and the sum of do not exceed over all test cases.

For each test case, output a binary string of length . The 'th character in the string should be if the answer holds true for the 'th farm.

样例输入 1

1
7 7 0 1

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

样例输出 1

111110

样例输入 2

1
6 6 0 2

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

样例输出 2

11010

样例输入 3

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

样例输出 3

111
000
1011

Sample 1 Explanation

Since is the only destination farm, the answer holds true if the 'th farm lies on any shortest path from to . There are two shortest paths from to , which are and .

Since there are no farms that already contain flower fields, the answer for farm holds true if farm lies on at least one of the two aforementioned paths.

Sample 2 Explanation

There are two destination farms: and . Since there are no farms that already contain flower fields, the 'th farm must lie on a shortest path to either or . Since farm lies on a shortest path to farm , so the answer holds for farm . Trivially, farm lies on the shortest path to farm and farm lies on the shortest path to farm .

Sample 3 Explanation

For the first test case, the answer holds true for the 'th farm if FJ can pass through farm , farm , and farm (in no particular order) on some shortest path to farm . It can be shown that the answer holds true for all farms.

SCORING:

• Inputs 4-6: and
• Inputs 7-9:
• Inputs 10-23: No additional constraints

Problem credits: Chongtian Ma