← 返回题目列表

Codeforces · 1530/G

G. 多么逆转

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

您有两个长度相等的字符串 $$$a$$$ 和 $$$b$$$,由字符 0 和 1 组成 $$$n$$$,以及一个整数 $$$k$$$。

您需要使字符串 $$$a$$$ 和 $$$b$$$ 相等。

在一步中,您可以选择 $$$a$$$ 中恰好包含 $$$k$$$ 个字符 1(以及任意数量的字符 0)的任意子字符串并将其反转。形式上,如果 $$$a = a_1 a_2 \ldots a_n$$$,则可以选择任何整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$),使得字符 $$$a_l、a_{l+1}、\ldots、a_r$$$ 中恰好有 $$$k$$$ 个,并将 $$$a$$$ 设置为$$$a_1 a_2 \l点a_{l-1} a_r a_{r-1} \l点a_l a_{r+1} a_{r+2} \l点a_n$$$。

找到一种方法,使用最多 $$$4n$$$ 上述类型的反转,使 $$$a$$$ 等于 $$$b$$$,或者确定这种方法不存在。不必最小化反转次数。

输入

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

每个测试用例由三行组成。每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le n$$$)。

第二行包含长度为 $$$n$$$ 的字符串 $$$a$$$。

第三行包含相同长度的字符串 $$$b$$$。两个字符串均由字符 0 和 1 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,如果在最多 $$$4n$$$ 反转中不可能使 $$$a$$$ 等于 $$$b$$$,则打印单个整数 $$$-1$$$。

否则,打印一个整数 $$$m$$$ ($$$0 \le m \le 4n$$$),表示步骤序列中的反转次数,后跟 $$$m$$$ 整数对 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$),表示$$$a$$$ 按时间顺序颠倒。每个子串在反转时必须恰好包含 $$$k$$$ 个。

请注意,$$$m$$$ 不必最小化。如果有多个答案,请打印其中一个。

示例

输入 #1

6
6 1
101010
010101
6 3
101010
010101
6 0
101010
010101
6 6
101010
010101
4 2
0000
1111
9 2
011100101
101001011

输出 #1

3
1 2
3 4
5 6
1
1 6
-1
-1
-1
5
4 8
8 9
3 6
1 4
3 6

注意

在第一个测试用例中,第一次反转后 $$$a = $$$ 011010,第二次反转后 $$$a = $$$ 010110,第三次反转后 $$$a = $$$ 010101。