← 返回题目列表

Codeforces · 1215/C

C. 交换字母

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

Monocarp 有两个长度相等的字符串 $$$s$$$ 和 $$$t$$$。两个字符串均由小写拉丁字母“a”和“b”组成。

Monocarp 希望使这两个字符串 $$$s$$$ 和 $$$t$$$ 彼此相等。他可以多次执行以下操作:在字符串$$$s$$$中选择索引$$$pos_1$$$,在字符串$$$t$$$中选择索引$$$pos_2$$$,并将$$$s_{pos_1}$$$与$$$t_{pos_2}$$$交换。

您必须确定 Monocarp 必须执行的最小操作数才能使 $$$s$$$ 和 $$$t$$$ 相等,并打印任何最佳操作序列 - 或者说不可能使这些字符串相等。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — $$$s$$$ 和 $$$t$$$ 的长度。

第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 字符“a”和“b”组成。

第三行包含一个字符串 $$$t$$$,由 $$$n$$$ 字符“a”和“b”组成。

输出

如果不可能使这些字符串相等,则打印 $$$-1$$$。

否则,在第一行打印 $$$k$$$ — 使字符串相等所需的最少操作数。在接下来的 $$$k$$$ 行中,打印两个整数 - 字符串 $$$s$$$ 中的索引和字符串 $$$t$$$ 中应在相应交换操作中使用的索引。

示例

输入 #1

4
abab
aabb

输出 #1

2
3 3
3 2

输入 #2

1
a
b

输出 #2

-1

输入 #3

8
babbaabb
abababaa

输出 #3

3
2 6
1 3
7 8

注意

在第一个示例中,两个操作就足够了。例如,您可以将 $$$s$$$ 中的第三个字母与 $$$t$$$ 中的第三个字母交换。然后$$$s = $$$“abbb”,$$$t = $$$“aaab”。然后交换 $$$s$$$ 中的第三个字母和 $$$t$$$ 中的第二个字母。那么 $$$s$$$ 和 $$$t$$$ 都等于“abab”。

在第二个示例中,不可能使两个字符串相等。