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

У Поликарпа есть $$$n$$$ различных бинарных слов. Слово называется бинарным, если состоит только из символов '0' и '1'. Например, следующие слова являются бинарными: «0001», «11», «0» и «0011100».

Поликарп хочет предложить этот набор из $$$n$$$ слов для игры в слова. Напомним, что это такая игра, во время которой игроки называют слова и каждое очередное слово (начиная со второго названного) начинается на тот же символ, что закончилось предыдущее слово. Первое названное слово может быть любым. Например, следующая последовательность слов может быть произнесена во время игры: «0101», «1», «10», «00», «00001».

Переворотом строки называется операция изменения порядка символов строки на обратный. Например, строка «0111» после переворота примет вид: «1110», а строка «11010» после переворота примет вид: «01011».

Возможно, набор слов Поликарпа такой, что не существует способа расположить их все в таком порядке, который согласуется с правилами игры. По этой причине Поликарп хочет перевернуть некоторые строки из заданного набора так, чтобы:

  • получившийся набор из $$$n$$$ строк всё еще содержал различные строки;
  • строки из получившегося набора можно расположить в таком порядке, чтобы полученная последовательность из $$$n$$$ строк была согласована с правилами игры.

Помогите Поликарпу выбрать минимальный набор строк, которые надо перевернуть.

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

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

В первой строке каждого набора содержится целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — количество строк в наборе Поликарпа. Следующие $$$n$$$ строк представляют собой строки набора. Все $$$n$$$ строк — непустые, состоят только из символов '0' и '1'. Сумма длин строк не превосходит $$$4\cdot10^6$$$. Все строки — различны.

Гарантируется, что сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$. Гарантируется, что сумма длин всех строк Поликарпа по всем наборам входных данных в тесте не превосходит $$$4\cdot10^6$$$.

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

Выведите ответы на $$$t$$$ наборов входных данных в порядке их следования.

Если ответа на набор входных данных не существует, то выведите -1. Иначе первая строка ответа должна содержать целое число $$$k$$$ ($$$0 \le k \le n$$$) — минимальное количество строк набора, которые надо перевернуть. Во вторую строку ответа выведите индексы $$$k$$$ строк, которые надо перевернуть. Строки нумеруются в порядке их записи во входных данных от $$$1$$$ до $$$n$$$. Если $$$k=0$$$, то вторую строку можно не выводить (или можно вывести пустую строку). Если ответов несколько, то выведите любой из них.

Пример
Входные данные
4
4
0001
1000
0011
0111
3
010
101
0
2
00000
00001
4
01
001
0001
00001
Выходные данные
1
3 
-1
0

2
1 2