CF1761E Make It Connected

给定一个包含 $n$ 个顶点的简单无向图。该图不包含自环，每对顶点之间最多只有一条边。你的任务很简单：使该图变为连通图。 你可以进行如下操作任意次（也可以不进行操作）： - 任意选择一个顶点 $u$。 - 对于图中每一个满足 $v\ne u$ 的顶点 $v$，如果 $v$ 与 $u$ 相邻，则删除 $u$ 与 $v$ 之间的边；否则，添加 $u$ 与 $v$ 之间的边。 请你求出使图变为连通图所需的最少操作次数。同时，输出任意一种长度为最少操作次数的操作序列，使图变为连通图。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1\leq t\leq 800$）——表示测试数据的组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$2\leq n\leq 4000$）——表示图中顶点的数量。 接下来有 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串 $s_i$，其中 $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$ 大于 $0$，则在下一行输出 $m$ 个整数，表示你在操作中选择的顶点编号。如果有多种最优解，输出任意一种即可。

在第一个测试点中，初始时图已经连通，因此答案为 $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$ 次操作使图连通。 由 ChatGPT 4.1 翻译