CF2254C2.Marenol (hard version)

This is the hard version of the problem. In this version, you are asked to determine the minimum number of operations to transform $a$ into $b$.

Yousef has given you two binary strings, $a$ and $b$, of the same length $n$.

You are allowed to perform any of the following operations:

• Choose a substring$^{\text{∗}}$ in $a$ equal to $\texttt{001}$ and replace it with $\texttt{100}$, or vice versa (i.e. $\texttt{001} \rightarrow \texttt{100}$ or $\texttt{100} \rightarrow \texttt {001}$).
• Choose a substring in $a$ equal to $\texttt{110}$ and replace it with $\texttt{011}$, or vice versa (i.e. $\texttt{011} \rightarrow \texttt{110}$ or $\texttt{110} \rightarrow \texttt {011}$).

Your task is to determine the minimum number of operations required to transform string $a$ into string $b$. If it is impossible to transform $a$ into $b$ using the given operations, output $-1$ instead.

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

这是该问题的困难版本。在本版本中，你需要确定将 $a$ 变换为 $b$ 所需的最少操作次数。

Yousef 给你两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。

你被允许执行以下任意一种操作：

• 在 $a$ 中选择一个等于 $\texttt{001}$ 的子串，并将其替换为 $\texttt{100}$；或者执行相反操作（即 $\texttt{001} \rightarrow \texttt{100}$ 或 $\texttt{100} \rightarrow \texttt{001}$）。
• 在 $a$ 中选择一个等于 $\texttt{110}$ 的子串，并将其替换为 $\texttt{011}$；或者执行相反操作（即 $\texttt{011} \rightarrow \texttt{110}$ 或 $\texttt{110} \rightarrow \texttt{011}$）。

你的任务是确定将字符串 $a$ 变换为字符串 $b$ 所需的最少操作次数。如果无法通过给定操作将 $a$ 变换为 $b$，则输出 $-1$。

$^{\text{∗}}$ 若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零个或全部）字符、并从结尾删除若干（可能为零个或全部）字符而得到，则称 $a$ 是 $b$ 的子串。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of each string.

The second line of each test case contains a binary string $a$ ($|a| = n$), consisting of only characters $\texttt{0}$ and/or $\texttt{1}$.

The third line of each test case contains a binary string $b$ ($|b| = n$), consisting of only characters $\texttt{0}$ and/or $\texttt{1}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 每个字符串的长度。

每个测试用例的第二行包含一个二进制字符串 $a$（$|a| = n$），仅由字符 $\texttt{0}$ 和/或 $\texttt{1}$ 组成。

每个测试用例的第三行包含一个二进制字符串 $b$（$|b| = n$），仅由字符 $\texttt{0}$ 和/或 $\texttt{1}$ 组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output the minimum number of operations required to transform $a$ into $b$. If it is impossible, output $-1$ instead.

对于每个测试用例，输出将 $a$ 变换为 $b$ 所需的最少操作次数。如果无法实现，则输出 $-1$。

In the first test case, we can choose the substring $a[2, 4] = \texttt{100}$ and replace it with $\texttt{001}$. This takes exactly $1$ operation.

In the second test case, it is impossible to transform $a$ into $b$, so the answer is $-1$.

In the third test case, we can do the following in order:

• $\texttt{1}$${\color{blue}{\texttt{100}}}$$\texttt{00}$ $\rightarrow$ $\texttt{1}$${\color{blue}{\texttt{001}}}$$\texttt{00}$
• $\texttt{100}$${\color{blue}{\texttt{100}}}$ $\rightarrow$ $\texttt{100}$${\color{blue}{\texttt{001}}}$
• ${\color{blue}{\texttt{100}}}$$\texttt{001}$ $\rightarrow$ ${\color{blue}{\texttt{001}}}$$\texttt{001}$
• $\texttt{00}$${\color{blue}{\texttt{100}}}$$\texttt{1}$ $\rightarrow$ $\texttt{00}$${\color{blue}{\texttt{001}}}$$\texttt{1}$

This takes $4$ operations. It can be shown that $4$ is the minimum answer.

在第一个测试用例中，我们可以选择子串 $a[2, 4] = \texttt{100}$ 并将其替换为 $\texttt{001}$。这恰好需要 $1$ 次操作。

在第二个测试用例中，无法将 $a$ 变换为 $b$，因此答案为 $-1$。

在第三个测试用例中，我们可以按如下顺序进行操作：

• $\texttt{1}$${\color{blue}{\texttt{100}}}$$\texttt{00}$ $\rightarrow$ $\texttt{1}$${\color{blue}{\texttt{001}}}$$\texttt{00}$
• $\texttt{100}$${\color{blue}{\texttt{100}}}$ $\rightarrow$ $\texttt{100}$${\color{blue}{\texttt{001}}}$
• ${\color{blue}{\texttt{100}}}$$\texttt{001}$ $\rightarrow$ ${\color{blue}{\texttt{001}}}$$\texttt{001}$
• $\texttt{00}$${\color{blue}{\texttt{100}}}$$\texttt{1}$ $\rightarrow$ $\texttt{00}$${\color{blue}{\texttt{001}}}$$\texttt{1}$

这总共需要 $4$ 次操作。可以证明 $4$ 是最小可能的答案。