У Поликарпа есть $$$n$$$ различных бинарных слов. Слово называется бинарным, если состоит только из символов '0' и '1'. Например, следующие слова являются бинарными: «0001», «11», «0» и «0011100».
Поликарп хочет предложить этот набор из $$$n$$$ слов для игры в слова. Напомним, что это такая игра, во время которой игроки называют слова и каждое очередное слово (начиная со второго названного) начинается на тот же символ, что закончилось предыдущее слово. Первое названное слово может быть любым. Например, следующая последовательность слов может быть произнесена во время игры: «0101», «1», «10», «00», «00001».
Переворотом строки называется операция изменения порядка символов строки на обратный. Например, строка «0111» после переворота примет вид: «1110», а строка «11010» после переворота примет вид: «01011».
Возможно, набор слов Поликарпа такой, что не существует способа расположить их все в таком порядке, который согласуется с правилами игры. По этой причине Поликарп хочет перевернуть некоторые строки из заданного набора так, чтобы:
Помогите Поликарпу выбрать минимальный набор строк, которые надо перевернуть.
В первой строке записано целое число $$$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
Название |
---|