CF2164D.Copy String

Given two strings $s$ and $t$ of length $n$, you aim to transform $s$ into $t$ through a series of the following operations:

• Construct a new string $s'$ of length $n$,where $s'_1=s_1$. For each $1 \lt i \le n$, $s'_i$ can be either $s_i$ or $s_{i-1}$. Then replace $s$ with $s'$.

Your task is to achieve this transformation using the minimum number of operations. You also need to output the solution by printing the constructed string $s'$ after each operation. If the transformation cannot be achieved in less than or equal to $k_{\mathrm{max}}$ operations, output -1.

给定两个长度为 $n$ 的字符串 $s$ 和 $t$，你需要通过一系列如下操作将 $s$ 变换为 $t$：

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

你的任务是使用最少的操作次数完成该变换。你还需要输出具体方案：每次操作后打印所构造的字符串 $s'$。若无法在不超过 $k_{\mathrm{max}}$ 次操作内完成变换，则输出 -1。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$, $k_{\mathrm{max}}$ ($1 \le n \cdot k_{\mathrm{max}} \le 10^6$) — the length of two strings and the maximum number of operations that can be used.

The second line of each test case contains one string $s$ of length $n$.

The third line of each test case contains one string $t$ of length $n$.

It is guaranteed that the sum of $nk_{\mathrm{max}}$ over all test cases does not exceed $10^6$.

It is guaranteed that both $s$ and $t$ consist of lowercase Latin letters.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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

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

For each test case:

• If you cannot achieve the transformation in less than or equal to $k_{\mathrm{max}}$ operations, simply output -1 in one line.
• Otherwise, on the first line, output one integer $k \le k_{\mathrm{max}}$ — the minimum number of operations. Then $k$ lines follow, each line contains one string of length $n$ — the string after each operation.

If there are multiple solutions, output any.

对于每个测试用例：

• 如果无法在不超过 $k_{\mathrm{max}}$ 次操作内完成该变换，则直接在一行中输出 -1。
• 否则，在第一行输出一个整数 $k \le k_{\mathrm{max}}$ —— 即所需的最少操作次数。随后输出 $k$ 行，每行包含一个长度为 $n$ 的字符串 —— 即每次操作后得到的字符串。

若存在多种可行解，输出任意一种即可。

In the first test case, obviously $s$ can be transformed to $t$ in one operation.

In the second test case, initially $s=t$, so no operation is needed.

In the fourth test case, although $s$ can be transformed to $t$ in two operations, but $k_{\mathrm{max}}=1$, so the answer is -1.

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

在第二个测试用例中，初始时 $s=t$，因此无需任何操作。

在第四个测试用例中，尽管 $s$ 可以通过两次操作转换为 $t$，但 $k_{\mathrm{max}}=1$，因此答案为 $-1$。