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

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

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выберите произвольную вершину $$$u$$$.
  • Для каждой вершины $$$v$$$, для которой $$$v\ne u$$$, если $$$v$$$ смежна с $$$u$$$, удалите ребро между $$$u$$$ и $$$v$$$, иначе добавьте ребро между $$$u$$$ и $$$v$$$.

Найдите минимальное количество операций, необходимых для того, чтобы сделать граф связным. Также найдите любую последовательность операций минимальной длины, которая делает граф связным.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 800$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 4000$$$) — количество вершин в графе.

Затем следуют $$$n$$$ строк. В $$$i$$$-й строке содержится бинарная строка $$$s_i$$$ длины $$$n$$$, где $$$s_{i,j}$$$ равно '1', если между вершинами $$$i$$$ и $$$j$$$ изначально существует ребро, иначе $$$s_{i,j}$$$ равно '0'.

Гарантируется, что $$$s_{i,i}$$$ всегда '0' и $$$s_{i,j}=s_{j,i}$$$ для $$$1\leq i,j\leq n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$4000$$$.

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

Для каждого набора входных данных в первой строке выведите целое число $$$m$$$  — минимально необходимое количество операций.

Если $$$m$$$ больше нуля, то выведите дополнительную строку, состоящую из $$$m$$$ целых чисел — вершин, выбранных в операциях в вашем решении. Если существует несколько решений с минимальным количеством операций, выведите любое из них.

Пример
Входные данные
4
3
011
100
100
3
000
001
010
4
0100
1000
0001
0010
6
001100
000011
100100
101000
010001
010010
Выходные данные
0
1
1
2
3 4 
3
2 5 6
Примечание

В первом наборе входных данных граф связен в начале, поэтому ответ  — $$$0$$$.

Во втором наборе входных данных, если мы выполним операцию с вершиной $$$1$$$, то получим следующий граф, представленный следующей матрицей смежности:

$$$$$$ \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} $$$$$$

Очевидно, что приведенный выше граф является связным.

В третьем наборе входных данных, если мы проделаем операцию с вершинами $$$3$$$ и $$$4$$$, то получим следующий граф, представленный следующей матрицей смежности:

$$$$$$ \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} $$$$$$

Очевидно, что приведенный выше граф является связным, и можно доказать, что мы не можем выполнить менее $$$2$$$ операций, чтобы сделать граф связным.