У вас есть особая версия меноры: она состоит из \(n\) свечей и некоторые из них уже зажжены. Мы можем описать, какие из свечей горят, с помощью бинарной строки \(s\), где \(i\)-я свечка горит тогда и только тогда, когда \(s_i=1\).
Первоначально, горящие свечки описаны строкой \(a\). За одну операцию, вы можете выбрать любую горящую в данный момент свечку — выбранная свеча продолжит гореть, а каждая из других свечей изменит свое состояние (если она горела, то потухнет, а если не горела — то загорится).
Вы хотите, чтобы в результате свечи горели так, как описывает строка \(b\). Ваша задача определить, возможно ли это и какое наименьшее количество операций нужно будет совершить.
Выходные данные
Для каждого набора входных данных выведите наименьшее количество операций, чтобы превратить \(a\) в \(b\), или же \(-1\), если это невозможно.
Примечание
В первом наборе входных данных, две строки уже равны, а потому нам не нужно применять ни одной операции.
Во втором наборе, мы можем применить одну операцию, выбрав вторую свечку, и превратить \(01\) в \(11\).
В третьем наборе, невозможно применить ни одной операции, потому что нет ни одной горящей свечи, которую можно выбрать.
В четвертом наборе, мы можем применить следующие операции, чтобы превратить \(a\) в \(b\):
- Выберем \(7\)-ю свечу: \(100010{\color{red}1}11\to 011101{\color{red} 1}00\).
- Выберем \(2\)-ю свечу: \(0{\color{red} 1}1101100\to 1{\color{red} 1}0010011\).
- Выберем \(1\)-ю свечу: \({\color{red}1}10010011\to {\color{red}1}01101100\).
В пятом наборе, мы можем применить следующие операции, чтобы превратить \(a\) в \(b\):
- Выберем \(6\)-ю свечу: \(00101{\color{red}1}011\to 11010{\color{red}1}100\)
- Выберем \(2\)-ю свечу: \(1{\color{red}1}0101100\to 0{\color{red}1}1010011\)
- Выберем \(8\)-ю свечу: \(0110100{\color{red}1}1\to 1001011{\color{red}1}0\)
- Выберем \(7\)-ю свечу: \(100101{\color{red}1}10\to 011010{\color{red}1}01\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
9
001011011
011010101
|
0
1
-1
3
4
|