这是本题的简单版本。两个版本之间的区别在于，在当前版本中，你只需要判断是否存在一个合法的操作序列。只有当你解决了本题的所有版本时，你才能进行 hack。

Kevin 有一个包含 $n$ 个顶点和 $m$ 条边的无向图。初始时，某些顶点上放有石子，Kevin 想要将它们移动到新的位置。

Kevin 可以进行以下操作：

• 对于每个位于 $u_i$ 的石子，选择一个相邻的顶点 $v_i$。同时将每个石子从 $u_i$ 移动到其对应的 $v_i$。

在任何时刻，每个顶点最多只能包含一个石子。

判断是否存在一个合法的操作序列，能够将石子从初始状态移动到目标状态。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 1000$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2000$, $0 \le m \le \min(\frac{n(n-1)}{2}, 10^4)$) —— 图中顶点和边的数量。

第二行包含一个由 '0' 和 '1' 组成的二进制字符串 $s$。$s$ 的第 $i$ 位表示初始状态下第 $i$ 个顶点上的石子数量。

第三行包含一个由 '0' 和 '1' 组成的二进制字符串 $t$。$t$ 的第 $i$ 位表示目标状态下第 $i$ 个顶点上的石子数量。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le 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