これは本問題のハードバージョンです。このバージョンとイージーバージョンの違いは、解が存在する場合に有効な操作手順を出力する必要がある点です。この問題のすべてのバージョンを解いた場合にのみ、ハックを行うことができます。

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

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

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

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

石を初期状態から目標状態へ移動させる有効な操作手順が存在するかどうかを判定してください。もし存在する場合、$2n$ 回以内の移動による有効な操作手順を出力してください。有効な操作手順が存在する場合、$2n$ 回以内の移動による有効な手順が存在することが証明できます。

入力

各テストケースは複数のテストケースを含みます。最初の行にはテストケースの数 $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" はすべて肯定的な回答として認識されます。

有効な操作手順が存在する場合、2 行目に操作回数を表す整数 $k$ ($0 \le k \le 2n$) を出力してください。初期状態に $c$ 個の石があるものとします。続く $k+1$ 行の各行には、操作前および各操作後の石の位置を表す $c$ 個の異なる整数を出力してください。これらの位置は以下を満たす必要があります。

• 最初の行の石の位置は、入力の初期状態と一致していること（順序は任意）。
• 最後の行の石の位置は、入力の目標状態と一致していること（順序は任意）。
• すべての $i$ ($1 \le i \le k$) および $j$ ($1 \le j \le c$) について、$i$ 行目の $j$ 番目の整数と $(i+1)$ 行目の $j$ 番目の整数がグラフ上で隣接していること。言い換えれば、石が前の位置から次の位置へ移動していること。

複数の解が存在する場合は、そのうちのいずれかを出力してください。

入出力例

入出力例 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

Yes
1
1 2
Yes
6
1 2 4 5 8 10
2 3 5 6 9 11
3 2 6 7 10 1
4 3 7 8 11 2
5 2 8 9 1 3
6 3 7 8 2 4
7 2 8 9 3 5
No
Yes
0
1 2 3