← 返回题目列表

Codeforces · 2164/D

D. 复制字符串

中文机器翻译题面 查看原题

给定两个长度为 $$$n$$$ 的字符串 $$$s$$$ 和 $$$t$$$,您的目标是通过以下一系列操作将 $$$s$$$ 转换为 $$$t$$$:

  • 构造一个长度为 $$$n$$$ 的新字符串 $$$s'$$$,其中 $$$s'_1=s_1$$$。对于每个 $$$1 \lt i \le n$$$,$$$s'_i$$$ 可以是 $$$s_i$$$ 或 $$$s_{i-1}$$$。然后将 $$$s$$$ 替换为 $$$s'$$$。

您的任务是使用 最小操作次数。您还需要通过在每次操作后打印构造的字符串 $$$s'$$$ 来输出解决方案。如果在小于或等于 $$$k_{\mathrm{max}}$$$ 运算中无法实现转换,则输出 -1.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$k_{\mathrm{max}}$$$ ($$$1 \le n \cdot k_{\mathrm{max}} \le 10^6$$$) — 两个字符串的长度和可以使用的最大操作数。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$。

每个测试用例的第三行包含一个长度为$$$n$$$的字符串$$$t$$$。

保证所有测试用例的$$$nk_{\mathrm{max}}$$$总和不超过$$$10^6$$$。

保证 $$$s$$$ 和 $$$t$$$ 均由小写拉丁字母组成。

输出

对于每个测试用例:

  • 如果无法在小于或等于 $$$k_{\mathrm{max}}$$$ 运算中实现转换,只需输出 -1 一行。
  • 否则,在第一行输出一个整数 $$$k \le k_{\mathrm{max}}$$$ — 最小运算次数。然后是 $$$k$$$ 行,每一行包含一个长度为 $$$n$$$ 的字符串——每次操作后的字符串。

如果有多个解,则输出任意一个。

示例

输入
复制

7
4 1
abcd
aabd
2 2
ab
ab
5 3
abcde
abbcc
9 1
egcnyeluw
eegccyelw
10 3
vzvylxxmsy
vvvvvllxxx
4 6
acba
aaac
5 7
acabb
aaaca

输出
复制

1
aabd
0
2
abbcd
abbcc
-1
3
vvzvylxxms
vvvzvllxxm
vvvvvllxxx
2
aacb
aaac
2
aacab
aaaca

注意

在第一个测试用例中,显然 $$$s$$$ 可以通过一次操作转换为 $$$t$$$。

在第二个测试用例中,最初$$$s=t$$$,所以不需要任何操作。

在第四个测试用例中,虽然$$$s$$$可以通过两次运算转化为$$$t$$$,但是$$$k_{\mathrm{max}}=1$$$,所以答案是 -1.