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

У Эврула есть бинарная строка $$$s$$$ длины $$$2n$$$. Бинарная строка — это строка, состоящая только из символов $$$0$$$ и $$$1$$$. Он хочет разбить $$$s$$$ на две непересекающиеся одинаковые подпоследовательности. Для этого ему нужна ваша помощь.

Вы можете выполнить следующую операцию один раз.

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

Другими словами, выберите последовательность индексов $$$b_1, b_2, \ldots, b_m$$$, где $$$1 \le b_1 < b_2 < \ldots < b_m \le 2n$$$. После этого одновременно присвойте $$$$$$s_{b_1} := s_{b_m},$$$$$$ $$$$$$s_{b_2} := s_{b_1},$$$$$$ $$$$$$\ldots,$$$$$$ $$$$$$s_{b_m} := s_{b_{m-1}}.$$$$$$

Можете ли вы разбить $$$s$$$ на две непересекающиеся одинаковые подпоследовательности после того, как выполните указанную операцию ровно один раз?

Разбиением $$$s$$$ на две непересекающиеся одинаковые подпоследовательности $$$s^p$$$ и $$$s^q$$$ называются два возрастающих массива индексов $$$p_1, p_2, \ldots, p_n$$$ и $$$q_1, q_2, \ldots, q_n$$$ такие, что каждое целое число от $$$1$$$ до $$$2n$$$ встречается $$$p$$$ и $$$q$$$ ровно один раз, при этом $$$s^p = s_{p_1} s_{p_2} \ldots s_{p_n}$$$, $$$s^q = s_{q_1} s_{q_2} \ldots s_{q_n}$$$, и $$$s^p = s^q$$$.

Если невозможно выполнить операцию и разбиение, выведите $$$-1$$$. Если можно выполнить операцию и разбить $$$s$$$ на две непересекающиеся подпоследовательности $$$s^p$$$ и $$$s^q$$$ так, чтобы $$$s^p = s^q$$$, выведите индексы подпоследовательности $$$b$$$ и индексы $$$s^p$$$, т. е. значения $$$p_1, p_2, \ldots, p_n$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$), где $$$2n$$$ — длина строки.

Вторая строка содержит бинарную строку $$$s$$$ длины $$$2n$$$.

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

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

Для каждого набора входных данных следуйте следующему формату.

Если решения не существует, выведите $$$-1$$$.

Иначе:

  • В первой строке выведите целое число $$$m$$$ ($$$0 \leq m \leq 2n$$$) и затем $$$m$$$ различных индексов в возрастающем порядке $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$.
  • Во второй строке выведите $$$n$$$ различных индексов в возрастающем порядке $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$.

Если существуют несколько решений, выведите любое из них.

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

В первом примере $$$b$$$ пустая, поэтому строка $$$s$$$ не меняется. Выберем $$$s^p = s_1 s_2 = \mathtt{10}$$$, тогда $$$s^q = s_3s_4 = \mathtt{10}$$$.

Во втором примере $$$b=[3,5]$$$. Изначально $$$s_3=\mathtt{0}$$$, и $$$s_5=\mathtt{1}$$$. После выполнения операции мы одновременно присваиваем $$$s_3=\mathtt{1}$$$ и $$$s_5=\mathtt{0}$$$.

Поэтому $$$s$$$ становится 101000 после выполнения операции.

Возьмем символы на позициях $$$[1,2,5]$$$ в $$$s^p$$$, получим $$$s_1=\mathtt{100}$$$. Символы на позициях $$$[3,4,6]$$$ будут в $$$s^q$$$, получим $$$s^q=100$$$. Это решение, потому что $$$s^p=s^q$$$.

В четвертом примере можно показать, что невозможно выполнить разбиение строки после любой операции.