← 返回题目列表

Codeforces · 1761/C

C. 套装构造

中文机器翻译题面 查看原题

给定一个由 $$$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 \neq Y$$$,则集合 $$$X$$$ 是集合 $$$Y$$$ 的真子集。

保证对于该问题中的所有测试用例,都存在这样的 $$$n$$$ 集。请注意,这并不意味着所有可能的输入都存在这样的 $$$n$$$ 集。

如果有多个解,则可以输出任意一个。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 100$$$)。

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

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

保证对于该问题中的所有测试用例,都存在这样的 $$$n$$$ 集。

输出

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

对于第 $$$i$$$ 行,首先输出 $$$s_i$$$ $$$(1 \le s_i \le n)$$$ — 集合 $$$A_i$$$ 的大小。然后,输出从 $$$1$$$ 到 $$$n$$$ 的不同整数 $$$s_i$$$ — 集合 $$$A_i$$$ 的元素。

如果有多个解,则可以输出任意一个。

保证对于该问题中的所有测试用例,都存在这样的 $$$n$$$ 集。

示例

输入 #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

注意

在第一个测试用例中,我们有 $$$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$$$ 的真子集。