← 返回题目列表

AtCoder · arc170_a

A. 又一个AB问题

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

分数: 400 点

问题陈述

给你两个字符串 S 和 T 长度 N 组成 A 和 B。让 S_i 表示 i从左边算起第一个字符 S.

您可以重复以下操作任意次数,可能为零:

  • 选择整数 i 和 j 这样 1\leq i < j \leq N。更换 S_i 与 A 和 S_j 与 B.

确定是否可以使 S 等于 T。如果可能的话,找出所需的最少操作次数。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 每个 S 和 T 是一个长度为 N 组成 A 和 B.
  • 所有输入数字均为整数。

输入

输入由标准输入按以下格式给出:

N
S
T

输出

如果不可能 S 等于 T,打印 -1.

否则,打印执行此操作所需的最少操作数。


示例输入 1

5
BAABA
AABAB

示例输出 1

2

执行操作 i=1 和 j=3 变化 S to AABBA.

执行操作 i=4 和 j=5 变化 S to AABAB.

因此,您可以使 S 等于 T 有两个操作。可以证明这是最少需要的运算次数,所以答案是 2.


示例输入 2

2
AB
BA

示例输出 2

-1

可以证明,无论执行多少次操作,都无法使 S 等于 T.