Make It Connected

Description:

Input:

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 800$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 4000$$$) — the number of vertices in the graph.

Then $$$n$$$ lines follow. The $$$i$$$-th row contains a binary string $$$s_i$$$ of length $$$n$$$, where $$$s_{i,j}$$$ is '1' if there is an edge between vertex $$$i$$$ and $$$j$$$ initially, otherwise $$$s_{i,j}$$$ is '0'.

It is guaranteed that $$$s_{i,i}$$$ is always '0' and $$$s_{i,j}=s_{j,i}$$$ for $$$1\leq i,j\leq n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4000$$$.

Output:

For each test case, in the first line, output an integer $$$m$$$  — the minimum number of operations required.

If $$$m$$$ is greater than zero, then print an extra line consisting of $$$m$$$ integers — the vertices chosen in the operations in your solution. If there are multiple solutions with the minimum number of operations, print any.

Sample Input:

4
3
011
100
100
3
000
001
010
4
0100
1000
0001
0010
6
001100
000011
100100
101000
010001
010010

Sample Output:

0
1
1
2
3 4 
3
2 5 6 

Note:

In the first test case, the graph is connected at the beginning, so the answer is $$$0$$$.

In the second test case, if we do the operation with vertex $$$1$$$, we will get the following graph represented by an adjacency matrix:

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

It's obvious that the graph above is connected.

In the third test case, if we do the operation with vertex $$$3$$$ and $$$4$$$, we will get the following graph represented by an adjacency matrix:

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

It's obvious that the graph above is connected, and it can be proven that we can't perform less than $$$2$$$ operations to make the graph connected.