[Solution] Mark and Lightbulbs Codeforces Solution

D. Mark and Lightbulbs

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Mark has just purchased a rack of n$n$ lightbulbs. The state of the lightbulbs can be described with binary string s=s1s2…sn$s=s_1{s}_2\dots s_n$, where si=1$s_i=\mathtt{\text{1}}$ means that the i$i$-th lightbulb is turned on, while si=0$s_i=\mathtt{\text{0}}$ means that the i$i$-th lightbulb is turned off.
Unfortunately, the lightbulbs are
broken, and the only operation he can perform to change the state of the lightbulbs is the following:

• Select an index i$i$ from 2,3,…,n−1$2,3,\dots ,n-1$ such that si−1≠si+1$s_{i-1}\ne s_{i+1}$.

• Toggle si$s_i$. Namely, if si$s_i$ is 0$\mathtt{\text{0}}$, set si$s_i$ to 1$\mathtt{\text{1}}$ or vice versa.

Mark wants the state of the lightbulbs to be another binary string t$t$. Help Mark determine the

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 minimum number of operations to do so.

Mark and the Online Exam Codeforces Solution

Mark and Professor Koro Codeforces Solution

Mark and Lightbulbs Codeforces Solution

Mark and His Unfinished Essay Codeforces Solution

Mark the Dust Sweeper Codeforces Solution

Mark the Photographer Codeforces Solution

The first line of the input contains a single integer q$q$ (1≤q≤104$1\le q\le {10}^4$) — the number of test cases.
The first line of each test case contains a single integer n$n$ (3≤n≤2⋅105$3\le n\le 2\cdot {10}^5$) — the number of lightbulbs.
The second line of each test case contains a binary string s$s$ of length n$n$ — the initial state of the lightbulbs.
The third line of each test case contains a binary string t$t$ of length n$n$ — the final state of the lightbulbs.
It is guaranteed that the sum of n$n$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$.
For each test case, print a line containing the minimum number of operations Mark needs to perform to transform s$s$ to t$t$. If there is no such sequence of operations, print −1$-1$.

Input

Output