Codeforces Round 847 (Div. 3) |
---|
Finished |
You are given an undirected connected graph, some vertices of which contain tokens and/or bonuses. Consider a game involving one player — you.
You can move tokens according to the following rules:
You can use different bonuses in any order. The same bonus can be used an unlimited number of times. Bonuses do not move during the game.
There can be several tokens in one vertex at the same time, but initially there is no more than one token in each vertex.
The vertex with number $$$1$$$ is the finish vertex, and your task is to determine whether it is possible to hit it with any token by making turns with the tiles according to the rules described above. If a token is initially located at the vertex of $$$1$$$, then the game is considered already won.
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of test cases in the test. The descriptions of the test cases follow.
The first line of the description of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph, respectively.
The second line of the description of each test case contains two integers $$$p$$$ and $$$b$$$ ($$$1 \le p \le n, 0 \le b \le n$$$) — the number of tokens and bonuses, respectively.
The third line of the description of each test case contains $$$p$$$ different integers from $$$1$$$ to $$$n$$$ — the indices of the vertices in which the tokens are located.
The fourth line of the description of each input data set contains $$$b$$$ different integers from $$$1$$$ to $$$n$$$ — the indices of the vertices in which the bonuses are located. Note that the value of $$$b$$$ can be equal to $$$0$$$. In this case, this line is empty.
There can be both a token and a bonus in one vertex at the same time.
The next $$$m$$$ lines of the description of each test case contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — vertices connected by the $$$i$$$-th edge. There is at most one edge between each pair of vertices. The given graph is connected, that is, from any vertex you can get to any one by moving along the edges.
The test cases are separated by an empty string.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of $$$m$$$ over all input data sets does not exceed $$$2 \cdot 10^5$$$.
For each test case, print YES in a separate line if you can reach the finish with some token, and NO otherwise.
You can output YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive response).
68 102 47 82 4 5 61 22 32 43 43 54 65 65 76 87 85 41 1531 22 33 44 52 11 021 24 31 223 41 22 32 45 43 25 3 42 41 22 33 44 51 01 111
YES NO YES YES YES YES
Name |
---|