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.

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 $ .

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

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.