这是问题的困难版本。版本之间的区别在于,在此版本中,您需要输出有效的操作序列(如果存在)。只有解决了该问题的所有版本,您才能破解。
Kevin 有一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。最初,一些顶点包含石头,凯文想要将其移动到新位置。
Kevin 可以执行以下操作:
- 对于 $$$u_i$$$ 处的每块石头,选择一个相邻顶点 $$$v_i$$$。同时将每块石头从 $$$u_i$$$ 移动到其对应的 $$$v_i$$$。
在任何时候,每个顶点最多可以包含一个石头。
确定是否存在将棋子从初始状态移动到目标状态的有效操作序列。输出一个有效的操作序列,移动次数不超过 $$$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$$$ 整数对应于图中的相邻顶点。换句话说,石头从前一个位置移动到下一个位置。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #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