CF1761E.Make It Connected

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.

给你一个由 $n$ 个顶点构成的简单无向图。该图不含自环，且任意两个顶点之间至多只有一条边。你的任务很简单：使该图连通。

你可以执行以下操作任意多次（包括零次）：

• 任选一个顶点 $u$；
• 对图中每个满足 $v \ne u$ 的顶点 $v$，若 $v$ 与 $u$ 相邻，则移除边 $(u, v)$；否则添加边 $(u, v)$。

求使图连通所需的最少操作次数。同时，构造出一个长度为该最小值的操作序列（即每次操作所选的顶点 $u$），使得最终图连通。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq 800$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\leq n\leq 4000$），表示图中顶点的数量。

接下来是 $n$ 行。第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $s_i$，其中若顶点 $i$ 与顶点 $j$ 之间初始存在一条边，则 $s_{i,j}$ 为 '1'，否则为 '0'。

保证对所有 $1\leq i,j\leq n$，均有 $s_{i,i}=$ '0' 且 $s_{i,j}=s_{j,i}$。

保证所有测试用例的 $n$ 值之和不超过 $4000$。

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.

对于每个测试用例，在第一行输出一个整数 $m$ —— 所需的最少操作次数。

如果 $m$ 大于零，则再输出一行，包含 $m$ 个整数 —— 即你在解法中所选择的操作顶点。若存在多种具有最少操作次数的解法，输出任意一种即可。

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.

在第一个测试用例中，图最初就是连通的，因此答案为 $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$ 次操作使该图连通。