给您一个无向连通图,其中一些顶点包含令牌和/或奖金。考虑一款涉及一名玩家(即您)的游戏。
您可以根据以下规则移动代币:
- 在游戏开始时,你可以进行一回合:将任何标记移动到任何相邻的顶点。
- 如果令牌的移动在奖金上结束,那么您可以使用任何其他令牌进行另一轮。
您可以按任意顺序使用不同的奖金。相同的奖金可以无限次使用。奖金在游戏过程中不会移动。
一个顶点中可以同时有多个令牌,但最初每个顶点中不超过一个令牌。
编号为$$$1$$$的顶点是终点顶点,你的任务是根据上述规则转动图块来确定是否可以用任何令牌击中它。如果令牌最初位于 $$$1$$$ 的顶点,则认为游戏已经获胜。
终点线为黑色,奖金为红色,筹码为灰色。
1. 从第 $$$8$$$ 个顶点移动到第 $$$6$$$ 个顶点。
2. 从第 $$$7$$$ 个顶点移动到第 $$$5$$$ 个顶点。
3. 从第 $$$6$$$ 个顶点移动到第 $$$4$$$ 个顶点。
4. 从第 $$$5$$$ 个顶点移动到第 $$$6$$$ 个顶点。
5. 从第 $$$4$$$ 个顶点移动到第 $$$2$$$ 个顶点。
6. 从第 $$$6$$$ 个顶点移动到第 $$$4$$$ 个顶点。
7. 从 $$$2$$$-nd 顶点移动到 $$$1$$$-st 顶点,即终点。
输入
输入数据的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果您可以使用某些令牌到达终点,则在单独的行中打印 YES,否则打印 NO。
在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。
示例
输入 #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
注意
- 第一个测试用例在语句中进行了解释。
- 在第二个测试用例中,只有一个令牌只能转一圈,并且无法到达终点。
- 在第三个测试用例中,代币可以在 $$$1$$$ 回合内到达终点线。
- 在第四个测试用例中,您只需从 $$$2$$$ 到 $$$1$$$ 转一圈。
- 在第六个测试用例中,令牌最初位于节点号 $$$1$$$ 处,因此我们立即获胜。