Set Construction
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, dfs and similar, graphs, greedy

You are given a binary matrix $$$b$$$ (all elements of the matrix are $$$0$$$ or $$$1$$$) of $$$n$$$ rows and $$$n$$$ columns.

You need to construct a $$$n$$$ sets $$$A_1, A_2, \ldots, A_n$$$, for which the following conditions are satisfied:

- Each set is nonempty and consists of distinct integers between $$$1$$$ and $$$n$$$ inclusive.
- All sets are distinct.
- For all pairs $$$(i,j)$$$ satisfying $$$1\leq i, j\leq n$$$, $$$b_{i,j}=1$$$ if and only if $$$A_i\subsetneq A_j$$$. In other words, $$$b_{i, j}$$$ is $$$1$$$ if $$$A_i$$$ is a proper subset of $$$A_j$$$ and $$$0$$$ otherwise.

Set $$$X$$$ is a proper subset of set $$$Y$$$, if $$$X$$$ is a nonempty subset of $$$Y$$$, and $$$X \neq Y$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. Note that it doesn't mean that such $$$n$$$ sets exist for all possible inputs.

If there are multiple solutions, you can output any of them.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases. The description of test cases follows.

The first line contains a single integer $$$n$$$ ($$$1\le n\le 100$$$).

The following $$$n$$$ lines contain a binary matrix $$$b$$$, the $$$j$$$-th character of $$$i$$$-th line denotes $$$b_{i,j}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

Output format:
For each test case, output $$$n$$$ lines.

For the $$$i$$$-th line, first output $$$s_i$$$ $$$(1 \le s_i \le n)$$$  — the size of the set $$$A_i$$$. Then, output $$$s_i$$$ distinct integers from $$$1$$$ to $$$n$$$  — the elements of the set $$$A_i$$$.

If there are multiple solutions, you can output any of them.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we have $$$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$$. Sets $$$A_1, A_2, A_3$$$ are proper subsets of $$$A_4$$$, and also set $$$A_2$$$ is a proper subset of $$$A_1$$$. No other set is a proper subset of any other set.

In the second test case, we have $$$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$$. $$$A_1$$$ is a proper subset of $$$A_2$$$ and $$$A_3$$$, and $$$A_2$$$ is a proper subset of $$$A_3$$$.

Example input:
2
4
0001
1001
0001
0000
3
011
001
000

Example output:
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3

Editorial:
Hint 1: When you are trying to add an element into a set $$$S$$$, you will have to add the element to every set that is meant to include $$$S$$$.
Hint 2: If $$$A$$$ does not include $$$B$$$, then $$$A$$$ and $$$B$$$ are already distinct.
If $$$A$$$ does include $$$B$$$, What is the easiest way of making $$$A$$$ and $$$B$$$ distinct?
Solution: Denote an ancestor to $$$S$$$ as a set that is meant to include $$$S$$$.
Denote a descendant to $$$S$$$ as a set that is meant to be included by $$$S$$$.
Let all sets be empty from the beginning.
Iterate through the sets. To make set $$$S$$$ distinct from its descendants, we can add a new number $$$x_S$$$ that hasn't been added to any previous sets to $$$S$$$ and all of its ancestors.
After the execution above, we will find out that the conditions are all satisfied, since:
- For all descendants of a set $$$S$$$, all the elements they have will be included in $$$S$$$;
- Vice versa for all ancestors of a set $$$S$$$;
- For each set $$$T$$$ that is not an ancestor nor a descendant to $$$S$$$, they will not include each other. This is because $$$S$$$ does not include $$$T$$$, since $$$S$$$ does not have the element $$$x_T$$$; and $$$T$$$ does not include $$$S$$$ for the same reason.
Therefore, the construction above satisfies all given conditions.
Moreover, we can set $$$x_S$$$ to the index of $$$S$$$ for a simpler implementation.