CF2061F2 Kevin and Binary String (Hard Version)

这是该问题的困难版本。两个版本的区别在于此版本中字符串 $ t $ 由 '0'、'1' 和 '?' 组成。只有当您解决了该问题的所有版本后才能进行 hack。 Kevin 有一个长度为 $ n $ 的二进制字符串 $ s $。Kevin 可以执行以下操作： - 选择 $ s $ 中两个相邻的块并交换它们。 块是指由相同字符组成的最大子串$ ^{\text{∗}} $。形式化定义：设 $ s[l,r] $ 为子串 $ s_l s_{l+1} \ldots s_r $。当满足以下条件时，$ s[l,r] $ 构成一个块： 1. $ l=1 $ 或 $ s_l \neq s_{l-1} $； 2. $ s_l = s_{l+1} = \ldots = s_r $； 3. $ r=n $ 或 $ s_r \neq s_{r+1} $。 相邻块是指两个块 $ s[l_1,r_1] $ 和 $ s[l_2,r_2] $ 满足 $ r_1 + 1 = l_2 $。 例如，若 $ s = \mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111} $，Kevin 可以选择块 $ s[4,5] $ 和 $ s[6,7] $ 进行交换，将 $ s $ 变为 $ \mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111} $。 给定一个由 '0'、'1' 和 '?' 组成且长度为 $ n $ 的字符串 $ t $，Kevin 希望确定使对于所有索引 $ i $（$ 1 \le i \le n $），若 $ t_i \neq $ '?' 则 $ s_i = t_i $ 所需的最小操作次数。若无法实现，输出 $ -1 $。 $ ^{\text{∗}} $ 若字符串 $ a $ 可通过从 $ b $ 的开头和结尾删除若干（可能为零或全部）字符得到，则称 $ a $ 是 $ b $ 的子串。

每个测试包含多个测试用例。第一行包含测试用例数量 $ t $（$ 1 \le t \le 10^4 $）。接下来是测试用例描述。 每个测试用例的第一行包含一个由 '0' 和 '1' 组成的字符串 $ s $。 每个测试用例的第二行包含一个由 '0'、'1' 和 '?' 组成的字符串 $ t $。 保证 $ s $ 和 $ t $ 的长度相同。 保证所有测试用例的 $ s $ 长度之和不超过 $ 4 \cdot 10^5 $。

对于每个测试用例，输出一个整数——所需的最小操作次数。若无法实现，输出 $ -1 $。

第一个示例的第一个测试用例的可能操作方式已在题目描述中展示。 第一个示例的第二个测试用例中，一种可能的操作方式为： 1. 交换块 $ [2, 2] $ 和 $ [3, 3] $，$ s $ 变为 $ \mathtt{001101} $； 2. 交换块 $ [3, 4] $ 和 $ [5, 5] $，$ s $ 变为 $ \mathtt{000111} $； 3. 交换块 $ [1, 3] $ 和 $ [4, 6] $，$ s $ 变为 $ \mathtt{111000} $。 第二个示例的第一个测试用例中，一种可能的操作方式为： 1. 交换块 $ [1, 1] $ 和 $ [2, 2] $，$ s $ 变为 $ \mathtt{100101} $； 2. 交换块 $ [4, 4] $ 和 $ [5, 5] $，$ s $ 变为 $ \mathtt{100011} $。 翻译由 DeepSeek R1 完成