题目描述

给定两个只包含 A 和 B 的长度为 $N$ 的字符串 $S$ 和 $T$。$S$ 的从左到右第 $i$ 个字符记作 $S_i$。

你可以任意次数（包括 $0$ 次）重复以下操作：

• 选择满足 $1 \leq i < j \leq N$ 的整数 $i, j$，将 $S_i$ 替换为 A，将 $S_j$ 替换为 B。

请判断是否可以通过若干次操作使 $S$ 变为 $T$，如果可以，求出所需的最小操作次数。

输入格式

输入以以下格式从标准输入读入：

$N$ $S$ $T$

输出格式

如果无法将 $S$ 变为 $T$，输出 -1。

如果可以，将 $S$ 变为 $T$ 的最小操作次数输出。

样例 1

输入

5
BAABA
AABAB

输出

2

样例 2

输入

2
AB
BA

输出

-1

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $S,T$ 均为只包含 A 和 B 的长度为 $N$ 的字符串
• 输入的所有数值均为整数

样例解释 1

第一次操作选择 $i=1, j=3$，$S$ 变为 AABBA。接着选择 $i=4, j=5$，$S$ 变为 AABAB。因此，$S$ 可以通过 $2$ 次操作变为 $T$，且这是最少的操作次数，所以答案为 $2$。

样例解释 2

无论进行多少次操作，都无法将 $S$ 变为 $T$。

由 ChatGPT 4.1 翻译