問題文

A, B のみからなる長さ N の文字列 S, T が与えられます。以下の操作を 0 回以上繰り返すことで S を T に一致させられるかを判定し、可能なら必要な操作回数の最小値を求めてください。

• S_i=S_{i+1} であるような整数 i\ (1 \leq i \lt N) を選び、S_i と S_{i+1} を A, B のうち現在とは異なる文字にそれぞれ置き換える。

制約

• 2 \leq N \leq 2 \times 10^5
• S, T は A, B のみからなる長さ N の文字列

入力例 1

3
AAB
BAA

出力例 1

2

例えば以下のような手順で操作を行うのが最善です。

• i=1 として操作を行う。S は BBB となる。
• i=2 として操作を行う。S は BAA となり、これは T に一致する。

入力例 2

3
ABA
AAA

出力例 2

-1

そもそも操作を一回も行うことができず、S を T に一致させることはできないため、-1 を出力します。

入力例 3

4
ABAB
ABAB

出力例 3

0

S と T が既に一致しているため、一度も操作を行う必要がありません。

原案: NatsubiSogan