这是问题的简单版本。版本之间的区别在于,在该版本中,您只需要判断是否存在有效的操作序列。只有解决了该问题的所有版本,您才能破解。
Kevin 有一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。最初,一些顶点包含石头,凯文想要将其移动到新位置。
Kevin 可以执行以下操作:
- 对于 $$$u_i$$$ 处的每个石头,选择一个相邻顶点 $$$v_i$$$。同时将每块石头从 $$$u_i$$$ 移动到其对应的 $$$v_i$$$。
在任何时候,每个顶点最多可以包含一个石头。
确定是否存在将棋子从初始状态移动到目标状态的有效操作序列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n \leq 2000$$$, $$$0\leq m \leq \min(\frac{n(n-1)}{2}, 10^4)$$$) — 图中顶点和边的数量。
第二行包含一个由“0”和“1”组成的二进制字符串$$$s$$$。 $$$s$$$的第$$$i$$$位表示初始状态下第$$$i$$$个顶点上的棋子数量。
第三行包含一个由“0”和“1”组成的二进制字符串$$$t$$$。 $$$t$$$的第$$$i$$$位表示目标状态下第$$$i$$$个顶点上的棋子数量。
接下来的 $$$m$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v \leq n$$$) - 第 $$$u$$$ 个顶点和第 $$$v$$$ 个顶点之间的无向边。
保证图形简单。图中不存在自环和平行边。
保证$$$s$$$和$$$t$$$中'1'的个数相同。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^4$$$。
输出
对于每个测试用例,在第一行输出“Yes”或“No”以指示是否存在有效的操作序列。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
4 2 1 10 01 1 2 11 11 11011001010 01101011100 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 1 3 2 110 101 1 2 2 3 3 2 111 111 1 2 2 3
输出 #1
Yes Yes No Yes