← 返回题目列表

Codeforces · 2061/H1

H1. 凯文和斯通斯 (简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在该版本中,您只需要判断是否存在有效的操作序列。只有解决了该问题的所有版本,您才能破解。

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