AT_arc207_e [ARC207E] Erase and Append

`0` と `1` のみからなる長さ $ N $ の文字列 $ s,t $ が与えられます。 以下の操作を $ 0 $ 回以上 $ N+1 $ 回以下行うことで $ s $ を $ t $ と一致させることが可能かどうかを判定し、可能な場合は操作列の一例を示してください。 操作：以下を順番に行う 1. $ 1 \le a,b \le N $ かつ $ |a-b|=1 $ を満たす整数 $ a,b $ を選ぶ 2. $ s $ の先頭から $ a $ 番目の文字を $ s $ の末尾に追加する 3. $ s $ の先頭から $ b $ 番目の文字を取り除き、残りの文字を元の順序を保って連結する $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ を空白区切りで出力せよ。

### Sample Explanation 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 $ は一致させることはできません。 ### Constraints - $ 1 \le T \le 10^{5} $ - $ 2 \le N \le 2 \times 10^{5} $ - $ s,t $ は長さ $ N $ の `0` と `1` のみからなる文字列 - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^{5} $ 以下