给你一个简单的无向图,由 $$$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$$$ 行。第 $$$i$$$ 行包含长度为 $$$n$$$ 的二进制字符串 $$$s_i$$$,其中如果顶点 $$$i$$$ 和 $$$j$$$ 之间最初存在边,则 $$$s_{i,j}$$$ 为“1”,否则 $$$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$$$ 整数组成的额外行 - 在解决方案的操作中选择的顶点。如果有多个具有最少操作次数的解决方案,则打印任何一个。
示例
输入 #1
4 3 011 100 100 3 000 001 010 4 0100 1000 0001 0010 6 001100 000011 100100 101000 010001 010010
输出 #1
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$$$ 的操作来使图连通。