CF1790G.Tokens on Graph

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:

• At the beginning of the game, you can make exactly one turn: move any token to any adjacent vertex.
• If the movement of the token ended on the bonus, then you are allowed to make another turn with any other token.

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 finish line is in black, the bonuses are in red, the chips are in grey.

For example, for a given graph, you can reach the finish line with a chip from the $8$th vertex by making the following sequence of turns:

1. Move from the $8$-th vertex to the $6$-th.
2. Move from the $7$-th vertex to the $5$-th.
3. Move from the $6$-th vertex to the $4$-th.
4. Move from the $5$-th vertex to the $6$-th.
5. Move from the $4$-th vertex to the $2$-nd.
6. Move from the $6$-th vertex to the $4$-th.
7. Move from the $2$-nd vertex to the $1$-st vertex, which is the finish.

给你一个无向连通图，其中某些顶点上放置有棋子和/或奖励点。考虑一个仅由一名玩家（即你）参与的游戏。

你可以按照以下规则移动棋子：

• 游戏开始时，你恰好可以进行一次操作：将任意一个棋子移动到其任意一个相邻顶点。
• 若该棋子的移动终点是一个奖励点，则你被允许再进行一次操作——即用任意其他棋子再执行一次移动。

你可以按任意顺序使用不同的奖励点；同一个奖励点可被重复使用任意多次。奖励点在游戏过程中位置固定，不会移动。

同一顶点上可同时存在多个棋子，但初始状态下每个顶点至多只有一个棋子。

编号为 $1$ 的顶点是终点，你的任务是判断：是否可以通过按上述规则进行操作，使得某个棋子最终到达顶点 $1$？若某个棋子初始时就位于顶点 $1$，则游戏视为已经获胜。

图中终点为黑色，奖励点为红色，棋子为灰色。

例如，在给定的图中，你可以通过以下操作序列，使位于第 $8$ 个顶点的棋子抵达终点：

1. 将棋子从第 $8$ 个顶点移至第 $6$ 个顶点；
2. 将棋子从第 $7$ 个顶点移至第 $5$ 个顶点；
3. 将棋子从第 $6$ 个顶点移至第 $4$ 个顶点；
4. 将棋子从第 $5$ 个顶点移至第 $6$ 个顶点；
5. 将棋子从第 $4$ 个顶点移至第 $2$ 个顶点；
6. 将棋子从第 $6$ 个顶点移至第 $4$ 个顶点；
7. 将棋子从第 $2$ 个顶点移至第 $1$ 个顶点（即终点）。

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

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的描述第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$），分别表示图中的顶点数和边数。

每个测试用例的描述第二行包含两个整数 $p$ 和 $b$（$1 \le p \le n$，$0 \le b \le n$），分别表示令牌数量和奖励数量。

每个测试用例的描述第三行包含 $p$ 个互不相同的整数，取值范围为 $1$ 到 $n$，表示令牌所在顶点的编号。

每个测试用例的描述第四行包含 $b$ 个互不相同的整数，取值范围为 $1$ 到 $n$，表示奖励所在顶点的编号。注意，$b$ 的值可能为 $0$；此时该行为空。

同一顶点上可以同时存在一个令牌和一个奖励。

每个测试用例描述的接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条边所连接的两个顶点。任意一对顶点之间至多存在一条边。给定图是连通的，即从任意顶点出发均可沿边到达其余任意顶点。

各测试用例之间以空行分隔。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$；同样，保证所有测试用例的 $m$ 之和不超过 $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).

对于每个测试用例，如果你能使用某个令牌到达终点，则在单独一行中输出 YES；否则输出 NO。

你可以以任意大小写形式输出 YES 和 NO（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

• The first test case is explained in the statement.

• In the second test case, there is only one token which can make only one turn, and it cannot reach the finish.

• In the third test case, the token can reach the finish line in $1$ turn.

• In the fourth test case, you need to make just one turn from $2$ to $1$.

• In the sixth test case, the token is initially at node number $1$, so we win immediately.

• 第一个测试用例已在题目描述中说明。

• 在第二个测试用例中，仅有一个棋子，它只能进行一次转向，且无法到达终点。

• 在第三个测试用例中，棋子可在 $1$ 轮内到达终点线。

• 在第四个测试用例中，你只需从节点 $2$ 向节点 $1$ 转向一次即可。

• 在第六个测试用例中，棋子初始位于节点 $1$，因此我们立即获胜。