Pinely Round 1 (Div. 1 + Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

constructive algorithms

dsu

graphs

greedy

matrices

trees

two pointers

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Make It Connected

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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

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

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.

Example

Input

430111001003000001010401001000000100106001100000011100100101000010001010010

Output

0 1 1 2 3 4 3 2 5 6

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 19:12:32 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|