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

Даны две бинарные строки $$$s$$$ и $$$t$$$, каждая из которых имеет одинаковую длину $$$n$$$. Вам разрешено выполнять следующую операцию:

  • Выберите индексы $$$l$$$, $$$r$$$ ($$$1 \le \color{red}{l \lt r} \le n$$$), такие что подстрока $$$s_{l,r}$$$ является палиндромом, и инвертируйте все биты в подстроке $$$s_{l,r}$$$.

Ваша цель состоит в том, чтобы в конечном итоге сделать $$$s$$$ равным $$$t$$$, выполнив вышеуказанную операцию не более $$$2n$$$ раз (возможно, ни разу).

Подстрока $$$s_{l,r}$$$ строки $$$s$$$ — это непрерывная последовательность символов, начинающаяся с индекса $$$l$$$ и заканчивающаяся на индексе $$$r$$$ (включительно), где $$$1 \leq l \lt r \leq |s|$$$. Здесь $$$|s|$$$ обозначает длину строки $$$s$$$.

Строка является палиндромом, если она читается одинаково слева направо и справа налево. Например, строки 101 и 00 являются палиндромами, в то время как 10 — нет.

Инвертирование всех битов в подстроке означает изменение каждого 0 на 1 и каждой 1 на 0 в этой подстроке. Например, инвертирование подстроки 101 приводит к 010.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$4 \le n \le 100$$$) — длина строк $$$s$$$ и $$$t$$$.

Следующие две строки каждого набора входных данных содержат бинарные строки $$$s$$$ и $$$t$$$, соответственно.

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

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

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

В противном случае первая строка должна содержать целое число $$$k$$$ ($$$0 \leq k \leq 2n$$$) — количество операций.

Для каждой из следующих $$$k$$$ строк выведите два целых числа $$$l, r$$$ ($$$1 \leq l \lt r \leq n$$$) — индексы, которые вы выбираете на каждой операции. Обратите внимание, что $$$s_{l,r}$$$ должен быть палиндромом на этом этапе.

Пример
Входные данные
3
5
01011
10000
7
1010101
0101010
4
0010
0010
Выходные данные
2
1 3
3 5
1
1 7
0
Примечание

Для первого набора входных данных:

  • Изначально, $$$s = \mathtt{01011}$$$ и $$$t = \mathtt{10000}$$$.
  • Сначала мы выбираем $$$l=1$$$ и $$$r=3$$$. Это допустимая операция, так как $$$s_{1,3} = \mathtt{010}$$$ является палиндромом. После инвертирования $$$s_{1,3}$$$ имеем $$$s = \mathtt{10111}$$$.
  • Затем мы выбираем $$$l=3$$$ и $$$r=5$$$. Это допустимая операция, так как $$$s_{3,5} = \mathtt{111}$$$ является палиндромом. После инвертирования $$$s_{3,5}$$$ имеем $$$s = \mathtt{10000}$$$.
  • Теперь $$$s$$$ равно $$$t$$$.

Для второго набора входных данных:

  • Изначально, $$$s = \mathtt{1010101}$$$ и $$$t = \mathtt{0101010}$$$.
  • Сначала мы выбираем $$$l=1$$$ и $$$r=7$$$. Это допустимая операция, так как $$$s_{1,7} = \mathtt{1010101}$$$ является палиндромом. После инвертирования $$$s_{1,7}$$$ имеем $$$s = \mathtt{0101010}$$$.
  • Теперь $$$s$$$ равно $$$t$$$.

Для третьего набора входных данных:

  • Изначально $$$s$$$ равно $$$t$$$. Операции не нужны.