给定一个由 $$$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$$$ 的真子集。