Make It Connected
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 2400
Tags: binary search, brute force, constructive algorithms, dsu, graphs, greedy, matrices, trees, two pointers

You are given a simple undirected graph consisting of $$$n$$$ vertices. The graph doesn't contain self-loops, there is at most one edge between each pair of vertices. Your task is simple: make the graph connected.

You can do the following operation any number of times (possibly zero):

- Choose a vertex $$$u$$$ arbitrarily.
- For each vertex $$$v$$$ satisfying $$$v\ne u$$$ in the graph individually, if $$$v$$$ is adjacent to $$$u$$$, remove the edge between $$$u$$$ and $$$v$$$, otherwise add an edge between $$$u$$$ and $$$v$$$.

Find the minimum number of operations required to make the graph connected. Also, find any sequence of operations with the minimum length that makes the graph connected.

Input format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

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.

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

Example output:
0
1
1
2
3 4 
3
2 5 6

Editorial:
Hint 1
Try to figure out the conditions where a task can be solved with $$$1$$$ operation. Then $$$2$$$ operations, and then even more operations.
Hint 2
The answer could be larger than $$$2$$$ only when the graph is made up of $$$2$$$ cliques, where you could only perform the operations on every vertex in the smaller clique to get the minimum number of operations.
Solution
First of all, we need to check if the graph is already connected at the beginning. If so, the answer would be $$$0$$$.
Otherwise, there will be more than $$$1$$$ connected component. If there exists a vertex that is the only vertex required to be operated to make the graph connected, we call such a vertex "feasible vertex". We may find out that a feasible vertex can only appear in a connected component that is not a clique.
But actually, there will always be such a vertex in a non-clique component. To prove this, we may figure out the sufficient condition for being a feasible vertex first.
The sufficient condition is that, if a vertex is not a cut vertex, and it is not adjacent to all other vertices in the connected component, then it must be a feasible vertex. We can prove that such a vertex always exists in a non-clique component. Here is the proof:
• Firstly, if there exist non-cut vertices that are adjacent to all other vertices in the component, we erase them one by one until there don't exist any non-cut vertices which are adjacent to all other vertices (note that a non-cut vertex which is adjacent to all other vertices may become a cut vertex after erasing some of the other vertices). Apparently, the remaining component would still be a non-clique component. Otherwise, the component could only be a clique from the beginning, which contradicts the premise.
• Then, we will find a non-cut vertex in the remaining component, since that vertices in a graph couldn't be all cut vertices. The non-cut vertex we found is the vertex we are searching for.
But implementing it directly (meaning using Tarjan's algorithm to find a non-cut vertex) might not be the easiest way to solve the problem. Actually, the vertex with the least degree in a connected component always satisfy the condition. We would like to leave the proof work of the alternative method to you.
Now we have proven that, if there exists a connected component that is not a clique, then the answer would be at most $$$1$$$. What if all connected components are cliques?
If there are exactly $$$2$$$ connected components, then apparently we will have to operate on all vertices in a connected component. So we'll choose the smaller connected component to operate, and the answer is exactly the size of it.
Otherwise, we can arbitrarily choose two vertices from two different connected components and operate on them. The answer is $$$2$$$.
Note that we also need to deal with isolated vertices (meaning vertices that are not adjacent to any other vertices) separately.