← 返回题目列表

AtCoder · arc207_e

E. 擦除和追加

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你字符串 s 和 t 长度 N 组成 0 和 1。 判断是否可以制作 s 匹配 t 至少执行以下操作 0 最多 N+1 次,如果可能的话,显示一个这样的操作序列。

操作:按顺序执行以下操作。

  1. 选择整数 a 和 b 满意 1 \le a,b \le N 和 |a-b|=1
  2. 附加 a- 从开头算起的第一个字符 s 到年底 s
  3. 删除 b- 从开头算起的第一个字符 s 并按原始顺序连接其余字符

你被给予 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

输出

按照给出的顺序打印给定测试用例的答案。 如果无法制作 s 匹配 t 通过至少执行操作 0 最多 N+1 次,打印 -1。 如果可能的话,首先打印操作次数 K,并在 j- 以下各项 K 行,打印两个整数 a_j 和 b_j 选择于 j第一个操作,以空格分隔。


示例输入 1

3
5
00101
00010
2
01
01
2
00
11

示例输出 1

1
2 3
0
-1

在第一个测试用例中, s is 00101 和 t is 00010.

  • 通过选择 2 和 3 as a 和 b,附加 2-nd 字符 0 到年底 s,然后删除 3-rd 字符,我们可以制作 s 和 t 匹配。
  • 请注意,整数 a 和 b 在操作中选择必须满足 |a-b|=1.

在第二个测试用例中, s 和 t 可以与零运算相匹配。

在第三个测试用例中,无论如何执行操作, s 和 t 无法匹配。