← 返回题目列表

AtCoder · arc216_a

A. 黑白棋 3

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你字符串 A 和 B 长度 N 组成 0 和 1。让 A_i 表示 i- 第一个字符 A.

您可以执行以下操作任意次数,可能为零。

  • 选择一个整数 i\ (2 \leq i \leq N-1) 满意 A_{i-1} = A_{i+1},然后翻转 A_i (更改 1 to 0 or 0 to 1).

确定是否可以使 A 等于 B 通过重复操作,如果是,求所需的最少操作次数。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 3 \leq N \leq 10^6
  • A 和 B 是长度的字符串 N 组成 0 和 1.
  • 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

对于第一个测试用例,您可以 A 等于 B 分两次操作如下。

  1. 选择 i = 2. A 变为 0101.
  2. 选择 i = 3. A 变为 0111.

对于第二个测试用例,不可能使 A 等于 B 无论你如何操作。