Problem Description

Given a string $ S $ and $ T $ of length $ N $ consisting only of characters A and B. Determine if $ S $ can be made to match $ T $ by performing the following operation zero or more times, and if possible, find the minimum number of operations required.

• Choose an integer $i\ (1\ \leq\ i\ \lt\ N)$ such that $ S_i=S_{i+1} $, and replace both $ S_i $ and $ S_{i+1} $ with the character different from their current one (A to B or B to A).

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ T $

Output Format

If $ S $ can be made to match $ T $ by the operations described in the problem, output the minimum number of operations required; otherwise, output -1.

Sample Input and Output

Sample Input #1

3
AAB
BAA

Sample Output #1

2

Sample Input #2

3
ABA
AAA

Sample Output #2

-1

Sample Input #3

4
ABAB
ABAB

Sample Output #3

0

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $ S $ and $ T $ are strings of length $ N $ consisting only of characters A and B.

Sample Explanation 1

For example, the best procedure is as follows:
- Perform the operation with $ i=1 $. $ S $ becomes BBB.
- Perform the operation with $ i=2 $. $ S $ becomes BAA, which matches $ T $.

Sample Explanation 2

Since no operations can be performed and $ S $ cannot be made to match $ T $, output -1.

Sample Explanation 3

Since $ S $ and $ T $ already match, no operations are needed.

Original idea: NatsubiSogan

见题面 Input 部分

见题面 Output 部分