What a Reversal

题意翻译

### 题目描述 - 给出两个 01 串 $a,b$，长度为 $n$。 - 一个合法的操作是反转 $a$ 的一个恰好有 $k$ 个 1 的子串。 - 求出满足题意的操作数 $m$ （应保证 $4n\ge m$）并构造一种操作，或者输出 $-1$ 表示无解。 - $n,k\le 2000$，测试组数 $t\le 2000$。 ### 输入格式 第一行，一个整数 $t$ （$1 \leq t \leq 2000$）。接下来有 $t$ 组数据，每一组数据的第一行输入 $n$ ， $k$（$1 \leq n \leq 2000;0 \leq k \leq n$）。接下来两行输入字符串 $a$ 和 $b$。 ### 输出格式 对于每一组数据，输出最少需要的反转次数 $m$，接下来 $m$ 行输出 $l$ 和 $r$，表示把字符串 $a$ 的第 $l$ 位至第 $r$ 位的字串反转 ，如果 $m > 4n$，就输出 $-1$。 ### 说明/提示 在第一组数据中，字符串 $a$ 经过第一次反转后，$a=011010$ ，第二次反转后， $a=010110$ ，第三次反转后， $a=010101$ 。 #### 翻译人：[imagination](https://www.luogu.com.cn/user/110009)

题目描述

You have two strings $ a $ and $ b $ of equal length $ n $ consisting of characters 0 and 1, and an integer $ k $ . You need to make strings $ a $ and $ b $ equal. In one step, you can choose any substring of $ a $ containing exactly $ k $ characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if $ a = a_1 a_2 \ldots a_n $ , you can choose any integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) such that there are exactly $ k $ ones among characters $ a_l, a_{l+1}, \ldots, a_r $ , and set $ a $ to $ a_1 a_2 \ldots a_{l-1} a_r a_{r-1} \ldots a_l a_{r+1} a_{r+2} \ldots a_n $ . Find a way to make $ a $ equal to $ b $ using at most $ 4n $ reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2000 $ ). Description of the test cases follows. Each test case consists of three lines. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2000 $ ; $ 0 \le k \le n $ ). The second line contains string $ a $ of length $ n $ . The third line contains string $ b $ of the same length. Both strings consist of characters 0 and 1. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

输出格式

For each test case, if it's impossible to make $ a $ equal to $ b $ in at most $ 4n $ reversals, print a single integer $ -1 $ . Otherwise, print an integer $ m $ ( $ 0 \le m \le 4n $ ), denoting the number of reversals in your sequence of steps, followed by $ m $ pairs of integers $ l_i, r_i $ ( $ 1 \le l_i \le r_i \le n $ ), denoting the boundaries of the substrings of $ a $ to be reversed, in chronological order. Each substring must contain exactly $ k $ ones at the moment of reversal. Note that $ m $ doesn't have to be minimized. If there are multiple answers, print any.

输入输出样例

输入样例 #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

说明

In the first test case, after the first reversal $ a = $ 011010, after the second reversal $ a = $ 010110, after the third reversal $ a = $ 010101.