これはこの問題のイージーバージョンです。このバージョンとハードバージョンの違いは、このバージョンでは有効な操作手順が存在するかどうかを判定するだけでよいという点です。この問題のすべてのバージョンを解いた場合にのみ、ハックを行うことができます。

Kevin は $n$ 個の頂点と $m$ 個の辺を持つ無向グラフを持っています。最初、いくつかの頂点には石が置かれており、Kevin はそれらを新しい位置に移動させたいと考えています。

Kevin は以下の操作を行うことができます。

• 各石について、その石がある頂点 $u_i$ に隣接する頂点 $v_i$ を選択する。すべての石を同時に $u_i$ から対応する $v_i$ へ移動させる。

どの時点においても、各頂点には最大で 1 つの石しか置くことができません。

初期状態から目標状態へ石を移動させる有効な操作手順が存在するかどうかを判定してください。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 1000$) が含まれます。 各テストケースの記述は以下の通りです。

各テストケースの最初の行には、グラフの頂点数と辺数を表す 2 つの整数 $n$ と $m$ ($1 \le n \le 2000, 0 \le m \le \min(\frac{n(n-1)}{2}, 10^4)$) が含まれます。

2 行目には ‘0’ と ‘1’ からなる二進文字列 $s$ が含まれます。$s$ の $i$ 番目のビットは、初期状態における $i$ 番目の頂点の石の有無を表します。

3 行目には ‘0’ と ‘1’ からなる二進文字列 $t$ が含まれます。$t$ の $i$ 番目のビットは、目標状態における $i$ 番目の頂点の石の有無を表します。

続く $m$ 行の各行には、2 つの整数 $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