CF2158D Palindrome Flipping

You are given two binary strings $ s $ and $ t $ , each of the same length $ n $ . You are allowed to perform the following operation: - Pick indices $ l $ , $ r $ ( $ 1 \le \color{red}{l < r} \le n $ ) such that substring $ s_{l,r} $ is a palindrome and flip all bits in substring $ s_{l,r} $ . The goal is to finally make $ s $ equal to $ t $ , performing any of the above operations at most $ 2n $ times (possibly none). A substring $ s_{l,r} $ of a string $ s $ is the contiguous sequence of characters starting from index $ l $ and ending at index $ r $ (both inclusive), where $ 1 \leq l < r \leq |s| $ . Here $ |s| $ denotes the length of the string $ s $ . A string is a palindrome if it reads the same forwards and backwards. For example, the strings 101 and 00 are palindromes, while 10 is not. Flipping all bits in a substring means changing each 0 to 1 and each 1 to 0 in that substring. For example, flipping the substring 101 results in 010.

Each test contains multiple test cases. The first line contains the number of test cases $ T $ ( $ 1 \le T \le 5\cdot 10^3 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 4 \le n \le 100 $ ) — the length of the strings $ s $ and $ t $ . The next two lines of each test case contain the binary strings $ s $ and $ t $ , respectively. It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 5\cdot 10^5 $ .

For each test case, if it is impossible to achieve the goal, print $ -1 $ . Otherwise, the first line should contain an integer $ k $ ( $ 0 \leq k \leq 2n $ ) — the number of operations. For each of the next $ k $ lines, print two integers $ l, r $ ( $ 1 \leq l < r \leq n $ ) — the indices you choose in each operation. Note that $ s_{l,r} $ must be a palindrome at this stage.

For the first test case: - Initially, $ s = \mathtt{01011} $ and $ t = \mathtt{10000} $ . - First, we choose $ l=1 $ and $ r=3 $ . This is a valid operation since $ s_{1,3} = \mathtt{010} $ is a palindrome. After flipping $ s_{1,3} $ , $ s = \mathtt{10111} $ . - Then, we choose $ l=3 $ and $ r=5 $ . This is a valid operation since $ s_{3,5} = \mathtt{111} $ is a palindrome. After flipping $ s_{3,5} $ , $ s = \mathtt{10000} $ . - Now, $ s $ is equal to $ t $ . For the second test case: - Initially, $ s = \mathtt{1010101} $ and $ t = \mathtt{0101010} $ . - First, we choose $ l=1 $ and $ r=7 $ . This is a valid operation since $ s_{1,7} = \mathtt{1010101} $ is a palindrome. After flipping $ s_{1,7} $ , $ s = \mathtt{0101010} $ . - Now, $ s $ is equal to $ t $ . For the third test case: - Initially, $ s $ is equal to $ t $ . No operations are needed.