CF1761C.Set Construction

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.

给你一个 $n$ 行 $n$ 列的二进制矩阵 $b$（矩阵中所有元素均为 $0$ 或 $1$）。

你需要构造 $n$ 个集合 $A_1, A_2, \ldots, A_n$，使得满足以下条件：

• 每个集合非空，且均由 $1$ 到 $n$（含端点）之间的互异整数构成；
• 所有集合互不相同；
• 对于所有满足 $1\leq i, j\leq n$ 的数对 $(i,j)$，$b_{i,j}=1$ 当且仅当 $A_i\subsetneq A_j$。换言之，当且仅当 $A_i$ 是 $A_j$ 的真子集时，$b_{i, j} = 1$；否则为 $0$。

集合 $X$ 是集合 $Y$ 的真子集，当且仅当 $X$ 是 $Y$ 的非空子集，且 $X \neq Y$。

本题保证：对所有测试用例，均存在满足要求的 $n$ 个集合。（注意：这并不意味着对所有可能的输入都存在这样的 $n$ 个集合。）

若存在多种解法，输出任意一种即可。

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.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。随后是各测试用例的描述。

第一行包含一个整数 $n$（$1\le n\le 100$）。

接下来的 $n$ 行包含一个二进制矩阵 $b$，其中第 $i$ 行的第 $j$ 个字符表示 $b_{i,j}$。

保证所有测试用例的 $n$ 之和不超过 $1000$。

保证本题中所有测试用例均存在满足条件的 $n$ 个集合。

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.

对于每个测试用例，输出 $n$ 行。

对于第 $i$ 行，首先输出 $s_i$ $(1 \le s_i \le n)$ —— 即集合 $A_i$ 的大小；然后输出 $s_i$ 个互不相同的、取值范围在 $1$ 到 $n$ 之间的整数 —— 即集合 $A_i$ 的元素。

若存在多种解法，输出任意一种即可。

本题保证：对所有测试用例，均存在满足条件的 $n$ 个集合。

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$.

在第一个测试用例中，我们有 $A_1 = {1, 2, 3}, A_2 = {1, 3}, A_3 = {2, 4}, A_4 = {1, 2, 3, 4}$。集合 $A_1, A_2, A_3$ 均为 $A_4$ 的真子集，且集合 $A_2$ 也是 $A_1$ 的真子集。其余任意两个集合之间均不存在真子集关系。

在第二个测试用例中，我们有 $A_1 = {1}, A_2 = {1, 2}, A_3 = {1, 2, 3}$。$A_1$ 是 $A_2$ 和 $A_3$ 的真子集，且 $A_2$ 是 $A_3$ 的真子集。