#arc119b. [arc119_b]Electric Board

[arc119_b]Electric Board

题目描述

一个电子布告栏正显示着一个长度为 NN 的字符串 SS,该字符串由 01 组成。

您可以执行以下操作任意次数,其中 SiS_i 表示布告栏上显示的字符串的第 ii 个字符 (1leqileqN)(1 \\leq i \\leq N)

**操作:**选择一对整数 (l,r)(l, r) (1leql<rleqN)(1 \\leq l < r \\leq N),满足以下条件之一,并交换 SlS_lSrS_r

  • Sl=S_l= 0,且 Sl+1=cdots=Sr=S_{l+1}=\\cdots=S_r= 1
  • Sl=cdots=Sr1=S_{l}=\\cdots=S_{r-1}= 1,且 Sr=S_r= 0

确定是否可能使布告栏上显示的字符串与 TT 匹配,并找出所需的最小操作次数(如果可能)。

约束条件

  • 2leqNleq5000002 \\leq N \\leq 500000
  • SS 是由 01 组成的长度为 NN 的字符串。
  • TT 是由 01 组成的长度为 NN 的字符串。

输入

输入以以下格式从标准输入给出:

NN

SS

TT

输出

如果无法使布告栏显示字符串 TT,则打印 -1

如果可能,找到所需的最小操作次数。


示例输入 1

7
1110110
1010111

示例输出 1

以下是让布告栏在两次操作后显示字符串 1010111 的一种可能方法:

  • (l,r)=(2,4)(l, r) = (2, 4) 执行操作,将布告栏上的字符串从 1110110 改为 1011110
  • (l,r)=(4,7)(l, r) = (4, 7) 执行操作,将布告栏上的字符串从 1011110 改为 1010111

示例输入 2

20
11111000000000011111
11111000000000011111

示例输出 2

在执行任何操作之前,布告栏上已经显示了字符串 TT,因此答案是 00


示例输入 3

6
111100
111000

示例输出 3

-1

如果没有一系列操作可以使布告栏显示字符串 TT,则打印 -1


示例输入 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

示例输出 4

22