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 < 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.

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.

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.

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.