AT_tupc2022_e 00-11 Rotation

0と1からなる長さ $N$ の文字列 $S, T$ が与えられます。 $S$ の $i$ 文字目を $S_i$ と表します。 あおばさんは文字列 $S$ に対して以下の2種類の操作を行うことで、 $S$ を $T$ に一致させたいです。 - 操作1: $S_iS_{i+1}S_{i+2}$ が $001, 100$ どちらかに等しいような $i(1 \leq i \leq N-2)$ を選ぶ。 そして、その3文字を $001, 100$ どちらかに置き換える。 - 操作2: $S_iS_{i+1}S_{i+2}$ が $110, 011$ どちらかに等しいような $i(1 \leq i \leq N-2)$ を選ぶ。 そして、その3文字を $110, 011$ どちらかに置き換える。 あおばさんは操作2は好きですが、操作1は嫌いです。 $S$ を $T$ に一致させるため操作1を最小何回行えば良いですか。 何回操作を行っても一致させることができない場合は -1 を出力してください。

入力は以下の形式で標準入力から与えられます。 ``` N S T ```

$S$ を $T$ に一致させるために必要な操作1の回数の最小値を整数で出力せよ。 一致させることが不可能な場合は -1 と出力せよ。

### Sample Explanation 1 まず、 $ i=5 $ として操作 $ 2 $ を行い、 $ S= $ `1011011` にします。 次に、 $ i=3 $ として操作 $ 2 $ を行い、 $ S= $ `1001111` にします。 最後に、 $ i=2 $ として操作 $ 1 $ を行い、 $ S= $ `1100111` にします。 これにより $ S $ を $ T $ と一致させることができました。操作 $ 1 $ を最低 $ 1 $ 回行う必要があるので答えは $ 1 $ です。 ### Sample Explanation 2 $ S $ と $ T $ を一致させることはできません。 ## 制約 - $3 \leq N \leq 3 \times 10^5$ - $N$ は整数である - $S, T$ は0,1からなる長さ $N$ の文字列