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.
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.
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$$$.
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.
from collections import deque
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for i in range(t):
    n = int(input())
    q = {}
    c = {}
    for j in range(1, n + 1):
        q[j] = []
        y = input().decode('utf-8')
        for k in range(1, n + 1):
            if y[k - 1] == '1':
                q[j].append(k)
        c[j] = len(q[j])
    res = []
    check = set()
    for j in range(1, n + 1):
        if j not in check:
            res.append([j])
            check.add(j)
            new = deque([j])
            while new:
                x = new.pop()
                for k in q[x]:
                    if k not in check:
                        check.add(k)
                        new.appendleft(k)
                        res[-1].append(k)
    rho = len(res)
    if rho == 1:
        print(0)
    elif rho == 2:
        for j in res:
            zeta = len(j)
            if zeta == 1:
                print(1)
                print(j[0])
                break
            mniota = zeta - 1
            mny = 0
            for k in j:
                if c[k] < mniota:
                    mniota = c[k]
                    mny = k
            if mniota < zeta - 1:
                print(1)
                print(mny)
                break
        else:
            mn = n
            delta = 0
            for j in range(rho):
                if mn >= len(res[j]):
                    mn = min(mn, len(res[j]))
                    delta = j
            print(mn)
            print(' '.join([str(k) for k in res[delta]]))
    else:
        for j in res:
            zeta = len(j)
            if zeta == 1:
                print(1)
                print(j[0])
                break
            mniota = zeta - 1
            mny = 0
            for k in j:
                if c[k] < mniota:
                    mniota = c[k]
                    mny = k
            if mniota < zeta - 1:
                print(1)
                print(mny)
                break
        else:
            print(2)
            print(res[0][0], res[1][0])
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
fii = lambda : map(float, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
mod = 998244353

def solve():
    n = ii()
    graph = []
    for i in range(n):
        graph.append(input())
    parents = list(range(n))

    def find(x):
        if x == parents[x]:
            return x
        else:
            parents[x] = find(parents[x])
            return parents[x]

    def merge(x, y):
        (x_, y_) = (find(x), find(y))
        parents[y_] = x_
    for i in range(n):
        for j in range(n):
            if graph[i][j] == '1':
                merge(i, j)
    d = {}
    for i in range(n):
        i_ = find(i)
        if i_ not in d:
            d[i_] = []
        d[i_].append(i)

    def is_complete(il):
        if len(il) < 2:
            return False
        else:
            for i in il:
                for j in il:
                    if i != j and graph[i][j] == '0':
                        return False
        return True

    def no_tarjan(il):
        if len(il) == 1:
            return il[0]
        min_de = len(il)
        min_i = -1
        for i in il:
            de = 0
            for j in il:
                if graph[i][j] == '1':
                    de += 1
            if de < min_de:
                min_de = de
                min_i = i
        return min_i
    if len(d) == 1:
        print(0)
        return
    elif len(d) == 2:
        (i1, i2) = d.keys()
        if is_complete(d[i1]):
            if is_complete(d[i2]):
                if len(d[i1]) < len(d[i2]):
                    print(len(d[i1]))
                    for i in range(len(d[i1])):
                        d[i1][i] += 1
                    print(*d[i1])
                else:
                    print(len(d[i2]))
                    for i in range(len(d[i2])):
                        d[i2][i] += 1
                    print(*d[i2])
            else:
                print(1)
                print(no_tarjan(d[i2]) + 1)
        else:
            print(1)
            print(no_tarjan(d[i1]) + 1)
    else:
        for i_ in d:
            if not is_complete(d[i_]):
                print(1)
                print(no_tarjan(d[i_]) + 1)
                break
        else:
            print(2)
            dl = list(d.keys())
            print(d[dl[0]][0] + 1, d[dl[1]][0] + 1)
for _ in range(ii()):
    solve()
from sys import stdin
input = lambda : stdin.readline()[:-1]
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

def check(n, mat, change, change2):
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if (mat[i][j] == '1') ^ (change == i or change == j) ^ (change2 == i or change2 == j):
                uf.union(i, j)
    grp = uf.all_group_members()
    if len(grp) != 1:
        raise Exception

def solve():
    n = int(input())
    mat = []
    uf = UnionFind(n)
    cnt = [0] * n
    for i in range(n):
        s = input()
        mat.append(s)
        for j in range(i + 1, n):
            if s[j] == '1':
                uf.union(i, j)
                cnt[i] += 1
                cnt[j] += 1
    grp = uf.all_group_members()
    if len(grp) == 1:
        print(0)
        return
    cmp = []
    for g_id in grp:
        g = grp[g_id]
        s = len(g)
        mn = s
        res = -1
        for v in g:
            if cnt[v] != s - 1:
                if cnt[v] < mn:
                    mn = cnt[v]
                    res = v
        if res != -1:
            print(1)
            print(res + 1)
            return
        cmp.append((s, g))
    cmp.sort()
    ans = cmp[0][1]
    if cmp[0][0] == 1:
        print(len(ans))
        print(*[i + 1 for i in ans])
        return
    if len(cmp) >= 3:
        print(2)
        ans = [cmp[0][1][0]] + [cmp[1][1][0]]
        x = ans[0]
        y = ans[1]
        print(*[i + 1 for i in ans][:2])
        return
    else:
        print(len(ans))
        print(*[i + 1 for i in ans])
for _ in range(int(input())):
    solve()