Binary Subsequence Rotation

题意翻译

## 题目描述 给定两个长度为$n$的$01$串$a$和$b$，要求串$a$的任意子序列经过若干次“旋转”操作变为串$b$ 对于一次“旋转操作”我们这样定义： 如果我们要旋转的序列为 $c_1,c_2,c_3,c_4,c_5...c_n$ 那么旋转之后的序列为$c_n,c_1,c_2,c_3,c_4...c_{n-1}$ 例如对于$s=1110100$ 如果我们旋转的子序列的下标为${2,6,7}$（从1开始） 那么旋转之后的串为$1010110 $ 求至少进行多少次“旋转”操作，能够把串$a$变成串$b$ ## 输入格式 输入一共三行 第一行输入一个整数$n(1≤n≤10^6)$ 第二行输入串$a$ 第三行输入串$b$ ## 输出格式 输出为$1$行，为最小的操作次数

题目描述

Naman has two binary strings $ s $ and $ t $ of length $ n $ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $ s $ into $ t $ using the following operation as few times as possible. In one operation, he can choose any subsequence of $ s $ and rotate it clockwise once. For example, if $ s = 1\textbf{1}101\textbf{00} $ , he can choose a subsequence corresponding to indices ( $ 1 $ -based) $ \{2, 6, 7 \} $ and rotate them clockwise. The resulting string would then be $ s = 1\textbf{0}101\textbf{10} $ . A string $ a $ is said to be a subsequence of string $ b $ if $ a $ can be obtained from $ b $ by deleting some characters without changing the ordering of the remaining characters. To perform a clockwise rotation on a sequence $ c $ of size $ k $ is to perform an operation which sets $ c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1} $ simultaneously. Determine the minimum number of operations Naman has to perform to convert $ s $ into $ t $ or say that it is impossible.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (1 \le n \le 10^6) $ — the length of the strings. The second line contains the binary string $ s $ of length $ n $ . The third line contains the binary string $ t $ of length $ n $ .

输出格式

If it is impossible to convert $ s $ to $ t $ after any number of operations, print $ -1 $ . Otherwise, print the minimum number of operations required.

输入输出样例

输入样例 #1

6
010000
000001

输出样例 #1

1

输入样例 #2

10
1111100000
0000011111

输出样例 #2

5

输入样例 #3

8
10101010
01010101

输出样例 #3

1

输入样例 #4

10
1111100000
1111100001

输出样例 #4

-1

说明

In the first test, Naman can choose the subsequence corresponding to indices $ \{2, 6\} $ and rotate it once to convert $ s $ into $ t $ . In the second test, he can rotate the subsequence corresponding to all indices $ 5 $ times. It can be proved, that it is the minimum required number of operations. In the last test, it is impossible to convert $ s $ into $ t $ .