C. Инверсия подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$, состоящие только из $$$0$$$ и $$$1$$$.

Вы можете выполнить следующую операцию над массивом $$$a$$$ любое количество раз:

  1. Выбрать $$$k$$$ индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$, где $$$1 \le k \le n$$$ и $$$\sum\limits_{j = 1}^k a_{i_j}$$$ нечётно. Другими словами, выбрать непустую подпоследовательность$$$^{\text{∗}}$$$ массива $$$a$$$ с нечётной суммой.
  2. Для каждого $$$1 \le j \le k$$$ присвоить $$$a_{i_j} = 1 - a_{i_j}$$$. Другими словами, инвертировать все элементы выбранной подпоследовательности.

Найдите минимальное количество операций, необходимое, чтобы превратить массив $$$a$$$ в массив $$$b$$$, или определите, что это невозможно.

$$$^{\text{∗}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массивов $$$a$$$ и $$$b$$$.

Во второй строке каждого набора входных данных даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — массив $$$a$$$.

В третьей строке каждого набора входных данных даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i \in \{0, 1\}$$$) — массив $$$b$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое, чтобы превратить массив $$$a$$$ в массив $$$b$$$, или $$$-1$$$, если это невозможно.

Пример
Входные данные
5
1
0
0
2
1 0
0 1
3
1 1 1
0 0 0
4
1 0 1 0
0 1 0 1
5
1 0 1 0 1
1 1 1 1 1
Выходные данные
0
1
1
2
-1
Примечание

В первом наборе входных данных $$$a = b$$$, поэтому не нужно выполнять операции, и ответ равен $$$0$$$.

Во втором наборе входных данных мы можем выполнить операцию с подпоследовательностью $$$[a_1, a_2]$$$. Сумма её элементов равна $$$1 + 0 = 1$$$, то есть является нечётной. Эта операция изменяет $$$a$$$ следующим образом: $$$[\color{red}{1, 0}] \rightarrow [\color{red}{0, 1}]$$$. Полученный массив равен $$$b$$$, поэтому ответ равен $$$1$$$.