/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
0 と 1 のみからなる長さ N の文字列 s,t が与えられます。
以下の操作を 0 回以上 N+1 回以下行うことで s を t と一致させることが可能かどうかを判定し、可能な場合は操作列の一例を示してください。
操作：以下を順番に行う
- 1 \le a,b \le N かつ |a-b|=1 を満たす整数 a,b を選ぶ
- s の先頭から a 番目の文字を s の末尾に追加する
- s の先頭から b 番目の文字を取り除き、残りの文字を元の順序を保って連結する
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 10^{5}
- 2 \le N \le 2 \times 10^{5}
- s,t は長さ N の
0と1のみからなる文字列 - 全てのテストケースにおける N の総和は 2 \times 10^{5} 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N s t
出力
与えられたテストケースに対し与えられた順に答えを出力せよ。
操作を 0 回以上 N+1 回以下行うことで s を t と一致させることが不可能ならば -1 を出力せよ。
可能ならば、はじめに操作回数 K を出力し、続く K 行のうち j 行目には j 回目の操作で選ぶ 2 つの整数 a_j,b_j を空白区切りで出力せよ。
入力例 1
3 5 00101 00010 2 01 01 2 00 11
出力例 1
1 2 3 0 -1
1 番目のテストケースにおいて s は 00101, t は 00010 です。
- a,b として 2,3 を選び、2 番目の文字である
0を s の末尾に追加した後、3 番目の文字を取り除くことで s と t を一致させることができます。 - 操作で選ぶ整数 a,b について |a-b|=1 である必要がある点に注意してください。
2 番目のテストケースにおいて、0 回の操作により s と t を一致させることができます。
3 番目のテストケースにおいて、どのように操作を行っても s と t は一致させることはできません。
Score : 800 points
Problem Statement
You are given strings s and t of length N consisting of 0 and 1.
Determine whether it is possible to make s match t by performing the following operation at least 0 and at most N+1 times, and if possible, show one such sequence of operations.
Operation: Perform the following in order.
- Choose integers a and b satisfying 1 \le a,b \le N and |a-b|=1
- Append the a-th character from the beginning of s to the end of s
- Remove the b-th character from the beginning of s and concatenate the remaining characters in their original order
You are given T test cases; find the answer for each of them.
Constraints
- 1 \le T \le 10^{5}
- 2 \le N \le 2 \times 10^{5}
- s and t are strings of length N consisting of
0and1. - The sum of N over all test cases is at most 2 \times 10^{5}.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N s t
Output
Print the answers for the given test cases in the order they are given.
If it is impossible to make s match t by performing the operation at least 0 and at most N+1 times, print -1.
If possible, first print the number of operations K, and on the j-th of the following K lines, print the two integers a_j and b_j chosen in the j-th operation, separated by a space.
Sample Input 1
3 5 00101 00010 2 01 01 2 00 11
Sample Output 1
1 2 3 0 -1
In the first test case, s is 00101 and t is 00010.
- By choosing 2 and 3 as a and b, appending the 2-nd character
0to the end of s, and then removing the 3-rd character, we can make s and t match. - Note that the integers a and b chosen in the operation must satisfy |a-b|=1.
In the second test case, s and t can be made to match with zero operations.
In the third test case, no matter how the operations are performed, s and t cannot be made to match.