你可能知道欧几里得是一位数学家。事实证明,墨菲斯也知道这一点。因此,当他想对欧几里得开一个卑鄙的把戏时,他给了他一个适当的噩梦。
在他的噩梦中,欧几里得在 $$$\mathbb{Z}_2$$$ 域上有一组 $$$S$$$ 的 $$$n$$$ $$$m$$$ 维向量,并且可以对它们执行向量加法。换句话说,他的向量具有 $$$m$$$ 坐标,每个向量要么等于 $$$0$$$ 要么 $$$1$$$。向量加法定义如下:设 $$$u+v = w$$$,则 $$$w_i = (u_i + v_i) \bmod 2$$$。
Euclid 可以对 $$$S$$$ 的任何子集求和,并在 $$$\mathbb{Z}_2$$$ 上归档另一个 $$$m$$$ 维向量。特别是,他可以将一个空子集求和;在这种情况下,生成的向量的所有坐标都等于 $$$0$$$。
令 $$$T$$$ 为所有向量的集合,这些向量可以写为来自 $$$S$$$ 的一些向量的总和。现在欧几里得想知道$$$T$$$的大小以及他是否可以仅使用$$$S$$$的子集$$$S'$$$来获得$$$T$$$中的所有向量。与通常的情况一样,在他弄清楚这一点之前,他不会醒来。到目前为止,对于这位哲学家来说,事情看起来相当严峻。但还是有希望的,因为他注意到 $$$S$$$ 中的所有向量最多有 $$$2$$$ 坐标等于 $$$1$$$。
帮助欧几里得计算 $$$|T|$$$,即 $$$\mathbb{Z}_2$$$ 上 $$$m$$$ 维向量的数量,这些向量可以写成来自 $$$S$$$ 的一些向量的总和。由于它可能非常大,请以 $$$10^9+7$$$ 为模进行计算。您还应该找到 $$$S'$$$,$$$S$$$ 的最小子集,$$$T$$$ 中的所有向量都可以写为来自 $$$S'$$$ 的向量之和。如果存在多个具有最少元素数量的此类集合,则根据输入中给出的元素的顺序输出字典顺序最小的集合。
考虑设置 $$$A$$$ 和 $$$B$$$ 使得 $$$|A| = |B|$$$。令 $$$a_1, a_2, \dots a_{|A|}$$$ 和 $$$b_1, b_2, \dots b_{|B|}$$$ 分别为 $$$A$$$ 和 $$$B$$$ 的索引元素递增数组。 $$$A$$$ 按字典顺序小于 $$$B$$$,当且仅当对于所有 $$$j < i$$$ 和 $$$a_i < b_i$$$ 存在 $$$i$$$ 且 $$$a_j = b_j$$$。
输入
输入的第一行有两个整数 $$$n$$$、$$$m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^5$$$) 分别表示 $$$S$$$ 中向量的个数和维数。
接下来的 $$$n$$$ 行包含 $$$S$$$ 中向量的描述。其中每个都有一个整数 $$$k$$$ ($$$1 \leq k \leq 2$$$),然后跟随 $$$k$$$ 不同的整数 $$$x_1, \dots x_k$$$ ($$$1 \leq x_i \leq m$$$)。这编码了一个 $$$m$$$ 维向量,在坐标 $$$x_1 上有 $$$1$$$s,在其余坐标上有 \dots x_k$$$ 和 $$$0$$$s。
在$$$n$$$向量中,没有两个是相同的。
输出
在第一行中,输出两个整数:$$$|T|$$$ 和 $$$|S'|$$$ 的模 $$$10^9+7$$$ 的余数。第二行,输出$$$|S'|$$$数字,即$$$S'$$$中元素的索引,按升序排列。 $$$S$$$ 的元素按照输入中给出的顺序从 $$$1$$$ 开始编号。
示例
输入 #1
3 2 1 1 1 2 2 2 1
输出 #1
4 2 1 2
输入 #2
2 3 2 1 3 2 1 2
输出 #2
4 2 1 2
输入 #3
3 5 2 1 2 1 3 1 4
输出 #3
8 3 1 2 3
注意
在第一个示例中,我们给出了三个向量:
- $$$10$$$
- $$$01$$$
- $$$11$$$
事实证明,我们可以使用这些向量表示 $$$2$$$ 维空间中的所有向量:
- $$$00$$$ 是上述向量的空子集的总和;
- $$$01 = 11 + 10$$$,是第一个和第三个向量的总和;
- $$$10 = 10$$$,只是第一个向量;
- $$$11 = 10 + 01$$$,是第一个和第二个向量的总和。
因此,$$$T = \{00, 01, 10, 11\}$$$。我们可以从$$$S$$$中选择三个向量中的任意两个,并且仍然能够获得$$$T$$$中的所有向量。在这种情况下,我们选择输入中首先出现的两个向量。由于我们无法仅使用 $$$S$$$ 中的单个向量来获取 $$$T$$$ 中的所有向量,因此 $$$|S'| = 2$$$ 和 $$$S' = \{10, 01\}$$$(索引 $$$1$$$ 和 $$$2$$$),因为集合 $$$\{1, 2 \}$$$ 按字典顺序是最小的。我们可以仅使用 $$$S'$$$ 中的向量来表示 $$$T$$$ 中的所有向量,如下所示:
- $$$00$$$ 是空子集的总和;
- $$$01 = 01$$$ 只是第二个向量;
- $$$10 = 10$$$ 只是第一个向量;
- $$$11 = 10 + 01$$$ 是第一个向量和第二个向量的总和。