A - Reversi 3 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

0 と 1 からなる長さ N の文字列 A,B が与えられます．A の i 文字目を A_i とします．

あなたは以下の操作を 0 回以上好きな回数行うことができます．

  • A_{i-1}=A_{i+1} を満たす整数 i\ (2\leq i\leq N-1) を選び，A_i を反転する（1 ならば 0 に，0 ならば 1 にする）．

操作を繰り返すことで A を B に一致させることができるか判定し，可能ならば一致させるために必要な操作回数の最小値を求めてください．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1\leq T\leq 2\times 10^5
  • 3\leq N\leq 10^6
  • A,B は 0 と 1 からなる長さ N の文字列
  • T,N は整数
  • 全てのテストケースに対する N の総和は 10^6 以下

入力

入力は以下の形式で標準入力から与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N
A
B

出力

\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T に対する答えを以下の形式で出力せよ．

A を B に一致させることができない場合，-1 と出力せよ．

一致させることができる場合，必要な操作回数の最小値を出力せよ．

入力例 1

4
4
0001
0111
6
101101
011100
5
10101
10101
10
0101000101
0011100111

出力例 1

2
-1
0
6

1 つ目のテストケースについて，以下のように 2 回の操作を行うことで A を B に一致させることができます．

  1. i = 2 を選ぶ．A は 0101 となる．
  2. i = 3 を選ぶ．A は 0111 となる．

2 つ目のテストケースについて，どのように操作しても A を B に一致させることはできません．

Score : 700 points

Problem Statement

You are given strings A and B of length N consisting of 0 and 1. Let A_i denote the i-th character of A.

You can perform the following operation any number of times, possibly zero.

  • Choose an integer i\ (2 \leq i \leq N-1) satisfying A_{i-1} = A_{i+1}, and flip A_i (change 1 to 0 or 0 to 1).

Determine whether you can make A equal to B by repeating the operation, and if so, find the minimum number of operations required.

You are given T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 3 \leq N \leq 10^6
  • A and B are strings of length N consisting of 0 and 1.
  • T and N are integers.
  • The sum of N over all test cases is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A
B

Output

Output the answers for \mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T in the following format.

If it is impossible to make A equal to B, print -1.

If it is possible, print the minimum number of operations required.

Sample Input 1

4
4
0001
0111
6
101101
011100
5
10101
10101
10
0101000101
0011100111

Sample Output 1

2
-1
0
6

For the first test case, you can make A equal to B in two operations as follows.

  1. Choose i = 2. A becomes 0101.
  2. Choose i = 3. A becomes 0111.

For the second test case, it is impossible to make A equal to B no matter how you operate.