CF1370E Binary Subsequence Rotation

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.

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