**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≤N≤2⋅105,N−1≤M≤2⋅105
). Initially, Farmer John is at his barn, represented by farm 1.
Initially, farms s1,s2,…,sK contain flower fields and farms d1,d2,…,dL 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 1and 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≤T≤100), the number of independent test cases.
The first line of each test case contains N, M, K, and L(0≤K≤N−1,1≤L≤N−1).
The following line contains s1,s2,…,sK ( 2≤ si ≤N, siare all distinct ).
The following line contains d1,d2,…,dL (2≤di≤N, di 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 106 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→2→3→4→5 and 1→2→3→6→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=0and L=1
Inputs 7-9: K=0
Inputs 10-23: No additional constraints
Problem credits: Chongtian Ma