Tokens on Graph

题意翻译

### 简述题意 给定一个 $n$ 个点 $m$ 条边的无向图。 每个点有特殊点与非特殊点之分。 每个点上可能会有若干个棋子，也可能没有棋子。 游戏开始时，你可以将任意一个棋子移到其相邻的点，如果棋子移动到的点是特殊点，你可以继续将任意其他棋子移到其相邻的点，否则游戏结束。 你需要判断：对于给定的无向图，给定的特殊点和棋子放置位置，玩一次游戏后，你能否让节点 $1$ 上有一个棋子。 $\sum n \le 2\times 10^5$，$\sum m \le 2\times 10^5$。 ### 输入格式 第一行一个正整数 $T$ 表示有 $T$ 组数据。 对于每组数据： 第一行有两个正整数分别表示 $n$，$m$。 下一行有两个正整数 $p$，$b$，表示有 $p$ 个棋子，$b$ 个特殊点。 下一行有 $p$ 个正整数，表示棋子初始位置。 下一行有 $b$ 个正整数，表示 $b$ 个特殊点。 接下来 $m$ 行每行两个正整数，表示 $m$ 条无向边。

题目描述

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.

输入输出格式

输入格式

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

输入输出样例

输入样例 #1

6
8 10
2 4
7 8
2 4 5 6
1 2
2 3
2 4
3 4
3 5
4 6
5 6
5 7
6 8
7 8


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


2 1
1 0
2


1 2


4 3
1 2
2
3 4
1 2
2 3
2 4


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


1 0
1 1
1
1

输出样例 #1

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是终点，你的任务是确定是否可以通过按照上述规则进行移动来让任何标记到达终点。如果标记最初位于顶点1，则游戏已经获胜。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数$ 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 $条边的顶点。每对顶点之间最多有一条边。给定的图是连通的，即你可以通过沿着边从一个顶点到达任何其他顶点。
- 测试用例之间由一个空行分隔。

**输出格式：**
- 对于每个测试用例，如果可以通过某些标记到达终点，则在一行中打印YES，否则打印NO。

**输入输出样例：**

**输入样例 #1：**
```
6
8 10
2 4
7 8
2 4 5 6
1 2
2 3
2 4
3 4
3 5
4 6
5 6
5 7
6 8
7 8
5 4
1 1
5
3
1 2
2 3
3 4
4 5
2 1
2
2 1
1 2
4 3
1 2
2
3 4
1 2
2 3
2 4
5 4
3 2
5 3 4
2 4
1 2
2 3
3 4
4 5
1 0
1 1
1
1
```

**输出样例 #1：**
```
YES
NO
YES
YES
YES
YES
```**题目大意：** 题目描述了一个游戏，你有一个包含标记和/或奖金的无向连通图。你可以根据以下规则移动标记： - 游戏开始时，你可以进行一次移动：将任何标记移动到任何相邻的顶点。 - 如果标记的移动结束在奖金顶点上，那么你可以使用另一个标记进行另一次移动。 你可以按任何顺序使用不同的奖金。同一个奖金可以使用无限次。在游戏过程中奖金不会移动。 一个顶点上可以同时有多个标记，但最初每个顶点上不超过一个标记。 顶点1是终点，你的任务是确定是否可以通过按照上述规则进行移动来让任何标记到达终点。如果标记最初位于顶点1，则游戏已经获胜。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数$ 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 $条边的顶点。每对顶点之间最多有一条边。给定的图是连通的，即你可以通过沿着边从一个顶点到达任何其他顶点。 - 测试用例之间由一个空行分隔。 **输出格式：** - 对于每个测试用例，如果可以通过某些标记到达终点，则在一行中打印YES，否则打印NO。 **输入输出样例：** **输入样例 #1：** ``` 6 8 10 2 4 7 8 2 4 5 6 1 2 2 3 2 4 3 4 3 5 4 6 5 6 5 7 6 8 7 8 5 4 1 1 5 3 1 2 2 3 3 4 4 5 2 1 2 2 1 1 2 4 3 1 2 2 3 4 1 2 2 3 2 4 5 4 3 2 5 3 4 2 4 1 2 2 3 3 4 4 5 1 0 1 1 1 1 ``` **输出样例 #1：** ``` YES NO YES YES YES YES ```