Kevin and Stones (Hard Version) - Problème

这是问题的困难版本。两个版本之间的区别在于，在这个版本中，如果存在合法的操作序列，你需要输出它。只有当你解决了这个问题的所有版本时，你才能进行 hack。

Kevin 有一个拥有 $n$ 个顶点和 $m$ 条边的无向图。最初，一些顶点上放有棋子，Kevin 想要将它们移动到新的位置。

Kevin 可以进行以下操作：

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

确定是否存在一个合法的操作序列，能够将棋子从初始状态移动到目标状态。如果存在，输出一个步数不超过 $2n$ 的合法操作序列。可以证明，如果存在合法的操作序列，则一定存在一个步数不超过 $2n$ 的合法操作序列。

每个测试点包含多个测试用例。第一行包含测试用例的数量 $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" 都会被识别为肯定的回答。

如果存在合法的操作序列，在第二行输出一个整数 $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$ 个整数在图中对应的顶点是相邻的。换句话说，棋子是从它上一次的位置移动到下一个位置的。

如果有多组解，输出其中任意一组即可。

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

QOJ.ac