H. Сбалансированные перевороты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Пошёл финальный раунд. Чтобы наконец сделать Вселенную идеально сбалансированной, вам нужно сделать строки $$$a$$$ и $$$b$$$ равными.

За один шаг вы можете выбрать любой префикс $$$a$$$ чётной длины и перевернуть его. Формально, если $$$a = a_1 a_2 \ldots a_n$$$, вы можете выбрать любое положительное чётное число $$$p \le n$$$ и сделать $$$a$$$ равной $$$a_p a_{p-1} \ldots a_1 a_{p+1} a_{p+2} \ldots a_n$$$.

Найдите способ сделать строки $$$a$$$ и $$$b$$$ равными, используя не более $$$n + 1$$$ переворотов такого рода, или определите, что такого способа не существует. Минимизировать число переворотов не нужно.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — число тестов.

Каждый тест состоит из двух строк. Первая строка содержит строку $$$a$$$ длины $$$n$$$, вторая строка содержит строку $$$b$$$ той же длины ($$$2 \le n \le 4000$$$; $$$n \bmod 2 = 0$$$). Обе строки состоят из символов 0 и 1.

Сумма $$$n$$$ по всем $$$t$$$ тестам не превосходит $$$4000$$$.

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

Для каждого теста, если невозможно сделать $$$a$$$ и $$$b$$$ равными, используя не более $$$n + 1$$$ переворотов, выведите число $$$-1$$$.

В противном случае выведите целое число $$$k$$$ ($$$0 \le k \le n + 1$$$) — число переворотов в вашей последовательности шагов, и $$$k$$$ чётных чисел $$$p_1, p_2, \ldots, p_k$$$ ($$$2 \le p_i \le n$$$; $$$p_i \bmod 2 = 0$$$) — длины префиксов $$$a$$$, которые нужно перевернуть, в хронологическом порядке.

Обратите внимание, что $$$k$$$ минимизировать не нужно. Если есть несколько решений, выведите любое из них.

Пример
Входные данные
4
0100011011
1101011000
10101010
10101010
0011
1001
100011
110010
Выходные данные
3
6 4 10
0

-1
7
2 6 2 6 2 2 6
Примечание

В первом тесте строка $$$a$$$ меняется следующим образом:

  • после первого переворота: 1000101011;
  • после второго переворота: 0001101011;
  • после третьего переворота: 1101011000.