CF2061H2.Kevin and Stones (Hard Version)

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

这是本题的困难版本。两个版本的区别在于，在此版本中如果存在有效操作序列，你需要输出具体的操作步骤。只有当你解决了本题所有版本时才能进行 Hack。

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

Kevin 可以执行以下操作：

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

请判断是否存在有效的操作序列可以将石子从初始状态移动到目标状态。若存在，请输出不超过 $2n$ 步的有效操作序列。可以证明，如果存在有效序列，则必然存在步数不超过 $2n$ 的有效序列。

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

如果存在有效操作序列，在第二行输出一个整数 $k$ （ $0 \leq k \leq 2n$ ）表示操作次数。假设初始状态有 $c$ 个石子，接下来的 $k + 1$ 行每行应包含 $c$ 个互不相同的整数，分别表示操作前及各次操作后的石子位置。这些位置需要满足以下条件：

第一行的石子位置必须与输入中的初始状态匹配，顺序可任意。
最后一行的石子位置必须与输入中的目标状态匹配，顺序可任意。
对于所有 $i$ （ $1 \leq i \leq k$ ）和 $j$ （ $1 \leq j \leq c$ ），确保第 $i$ 行第 $j$ 个整数与第 $i+1$ 行第 $j$ 个整数对应的顶点在图中是相邻的。换句话说，石子必须从其前一位置移动到下一位置。

如果存在多种解决方案，输出任意一种即可。

翻译由 DeepSeek R1 完成

输入#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
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

输入解题思路，AI测评打分。不知道怎么写?