E - Erase and Append Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800

問題文

01 のみからなる長さ N の文字列 s,t が与えられます。 以下の操作を 0 回以上 N+1 回以下行うことで st と一致させることが可能かどうかを判定し、可能な場合は操作列の一例を示してください。

操作:以下を順番に行う

  1. 1 \le a,b \le N かつ |a-b|=1 を満たす整数 a,b を選ぶ
  2. s の先頭から a 番目の文字を s の末尾に追加する
  3. s の先頭から b 番目の文字を取り除き、残りの文字を元の順序を保って連結する

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 10^{5}
  • 2 \le N \le 2 \times 10^{5}
  • s,t は長さ N01 のみからなる文字列
  • 全てのテストケースにおける N の総和は 2 \times 10^{5} 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
s
t

出力

与えられたテストケースに対し与えられた順に答えを出力せよ。 操作を 0 回以上 N+1 回以下行うことで st と一致させることが不可能ならば -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 番目のテストケースにおいて s00101, t00010 です。

  • a,b として 2,3 を選び、2 番目の文字である 0s の末尾に追加した後、3 番目の文字を取り除くことで st を一致させることができます。
  • 操作で選ぶ整数 a,b について |a-b|=1 である必要がある点に注意してください。

2 番目のテストケースにおいて、0 回の操作により st を一致させることができます。

3 番目のテストケースにおいて、どのように操作を行っても st は一致させることはできません。

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.

  1. Choose integers a and b satisfying 1 \le a,b \le N and |a-b|=1
  2. Append the a-th character from the beginning of s to the end of s
  3. 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 0 and 1.
  • 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 0 to 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.