Set Construction

题意翻译

### 题目描述 给你一个 $n\times n$ 的矩阵 $b$。 你需要构造 $n$ 个集合，集合里出现的数只能是 $1\sim n$。 若 $b_{i,j}=1$，则说明集合 $i$ 是集合 $j$ 的子集。否则说明集合 $i$ 不是集合 $j$ 的子集。 数据保证有解，你需要构造出这 $n$ 个集合。 ### 输入格式 第一行一个数字 $t(t\le 1000)$，说明有 $t$ 组数据。 对于每组数据，第一行一个数 $n(n\le 100)$。 第 $2\sim n+1$ 行每行 $n$ 个数为矩阵 $b$。 ### 输出格式 对于每组数据，输出 $n$ 行。 每一行的先输出该集合的元素数量，再输出该集合的元素。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

2
4
0001
1001
0001
0000
3
011
001
000

输出样例 #1

3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3

说明

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

**题目大意：**

题目要求根据给定的一个 $n \times n$ 的01矩阵 $b$，构造出 $n$ 个集合 $A_1, A_2, \ldots, A_n$，这些集合必须满足以下条件：

- 每个集合非空，并且由不同的整数组成，整数的范围是 $1$ 到 $n$。
- 所有集合都是不同的。
- 对于所有的 $i, j$（$1 \leq i, j \leq n$），当 $b_{i,j}=1$ 时，集合 $A_i$ 必须是集合 $A_j$ 的真子集；反之，当 $b_{i,j}=0$ 时，集合 $A_i$ 不是集合 $A_j$ 的子集。

题目保证对于所有测试用例，都存在这样的 $n$ 个集合。

**输入数据格式：**

每组数据的第一行是一个整数 $t$（$1 \le t \le 1000$），表示有 $t$ 组数据。

对于每组数据，第一行是一个整数 $n$（$1 \le n \le 100$）。

接下来的 $n$ 行，每行包含 $n$ 个数字，代表矩阵 $b$。

**输出数据格式：**

对于每组数据，输出 $n$ 行。

每行的第一部分是一个整数 $s_i$（$1 \le s_i \le n$），表示集合 $A_i$ 的元素数量。接着输出 $s_i$ 个从 $1$ 到 $n$ 的不同整数，代表集合 $A_i$ 的元素。

如果有多个解决方案，可以输出其中任何一个。**题目大意：** 题目要求根据给定的一个 $n \times n$ 的01矩阵 $b$，构造出 $n$ 个集合 $A_1, A_2, \ldots, A_n$，这些集合必须满足以下条件： - 每个集合非空，并且由不同的整数组成，整数的范围是 $1$ 到 $n$。 - 所有集合都是不同的。 - 对于所有的 $i, j$（$1 \leq i, j \leq n$），当 $b_{i,j}=1$ 时，集合 $A_i$ 必须是集合 $A_j$ 的真子集；反之，当 $b_{i,j}=0$ 时，集合 $A_i$ 不是集合 $A_j$ 的子集。 题目保证对于所有测试用例，都存在这样的 $n$ 个集合。 **输入数据格式：** 每组数据的第一行是一个整数 $t$（$1 \le t \le 1000$），表示有 $t$ 组数据。 对于每组数据，第一行是一个整数 $n$（$1 \le n \le 100$）。 接下来的 $n$ 行，每行包含 $n$ 个数字，代表矩阵 $b$。 **输出数据格式：** 对于每组数据，输出 $n$ 行。 每行的第一部分是一个整数 $s_i$（$1 \le s_i \le n$），表示集合 $A_i$ 的元素数量。接着输出 $s_i$ 个从 $1$ 到 $n$ 的不同整数，代表集合 $A_i$ 的元素。 如果有多个解决方案，可以输出其中任何一个。