CF958D2.Hyperspace Jump (hard)

It is now 125 years later, but humanity is still on the run from a humanoid-cyborg race determined to destroy it. Or perhaps we are getting some stories mixed up here... In any case, the fleet is now smaller. However, in a recent upgrade, all the navigation systems have been outfitted with higher-dimensional, linear-algebraic jump processors.

Now, in order to make a jump, a ship's captain needs to specify a subspace of the d-dimensional space in which the events are taking place. She does so by providing a generating set of vectors for that subspace.

Princess Heidi has received such a set from the captain of each of m ships. Again, she would like to group up those ships whose hyperspace jump subspaces are equal. To do so, she wants to assign a group number between 1 and m to each of the ships, so that two ships have the same group number if and only if their corresponding subspaces are equal (even though they might be given using different sets of vectors).

Help Heidi!

如今已是125年之后，但人类依然在逃亡——这次是逃离一支决心毁灭人类的人形机器人种族。抑或我们在此处混淆了某些故事……无论如何，舰队规模已大大缩减。然而，在最近的一次升级中，所有导航系统均已配备高维线性代数跳跃处理器。

现在，飞船船长若要执行一次跃迁，需指定事件所发生的 $d$ 维空间中的一个子空间，并通过提供该子空间的一组生成向量来完成指定。

公主海蒂已从 $m$ 艘飞船的船长处各自收到了这样一组生成向量。她再次希望将那些超空间跃迁子空间相同的飞船归为同一组。为此，她希望为每艘飞船分配一个介于 $1$ 到 $m$ 之间的组号，使得两艘飞船具有相同组号当且仅当它们对应的子空间完全相等（即使这些子空间由不同的向量组所给出）。

请帮助海蒂！

The first line of the input contains two space-separated integers m and d (2 ≤ m ≤ 30 000, 1 ≤ d ≤ 5) – the number of ships and the dimension of the full underlying vector space, respectively. Next, the m subspaces are described, one after another. The i-th subspace, which corresponds to the i-th ship, is described as follows:

The first line contains one integer k__i (1 ≤ k__i ≤ d). Then k__i lines follow, the j-th of them describing the j-th vector sent by the i-th ship. Each of the j lines consists of d space-separated integers a__j, j = 1, ..., d, that describe the vector ; it holds that |a__j| ≤ 250. The i-th subspace is the linear span of these k__i vectors.

输入的第一行包含两个以空格分隔的整数 $m$ 和 $d$（$2 \leq m \leq 30\,000$，$1 \leq d \leq 5$），分别表示飞船的数量以及底层完整向量空间的维数。接下来依次描述 $m$ 个子空间。第 $i$ 个子空间对应第 $i$ 艘飞船，其描述方式如下：

第一行包含一个整数 $k_i$（$1 \leq k_i \leq d$）。随后是 $k_i$ 行，其中第 $j$ 行描述第 $i$ 艘飞船发送的第 $j$ 个向量。每行包含 $d$ 个以空格分隔的整数 $a_{j,1},\, a_{j,2},\, \dots,\, a_{j,d}$（$j = 1,\, \dots,\, d$），用于描述向量 ；满足 $|a_{j}| \leq 250$。第 $i$ 个子空间即为这 $k_i$ 个向量所张成的线性子空间。

Output m space-separated integers _g_1, ..., g__m, where denotes the group number assigned to the i-th ship. That is, for any 1 ≤ i < j ≤ m, the following should hold: g__i = g__j if and only if the i-th and the j-th subspaces are equal. In addition, the sequence (_g_1, _g_2, ..., g__m) should be lexicographically minimal among all sequences with that property.

输出 m 个以空格分隔的整数 _g_1, ..., g__m，其中 表示分配给第 i 艘飞船的组号。即：对任意满足 1 ≤ i < j ≤ m 的 i, j，应有 g__i = g__j 当且仅当第 i 个与第 j 个子空间相等。此外，序列 (_g_1, _g_2, ..., g__m) 应在所有满足该性质的序列中字典序最小。

In the sample testcase, the first and the last subspace are equal, subspaces 2 to 4 are equal, and subspaces 5 to 7 are equal.

Recall that two subspaces, one given as the span of vectors and another given as the span of vectors , are equal if each vector v__i can be written as a linear combination of vectors w_1, ..., w__k (that is, there exist coefficients such that v__i = α1_w_1 + ... + α_k__w__k) and, similarly, each vector w__i can be written as a linear combination of vectors _v_1, ..., v__n.

Recall that a sequence (_g_1, _g_2, ..., g__m) is lexicographically smaller than a sequence (_h_1, _h_2, ..., h__m) if there exists an index i, 1 ≤ i ≤ m, such that g__i < h__i and g__j = h__j for all j < i.

在样例测试用例中，第一个子空间与最后一个子空间相等，第 2 至第 4 个子空间相等，第 5 至第 7 个子空间相等。

回顾：若两个子空间分别由向量组 和向量组 张成，则它们相等当且仅当每个向量 $v_i$ 均可表示为向量 $w_1,\dots,w_k$ 的线性组合（即存在系数 ，使得 $v_i = \alpha_1 w_1 + \dots + \alpha_k w_k$），且类似地，每个向量 $w_i$ 均可表示为向量 $v_1,\dots,v_n$ 的线性组合。

回顾：序列 $(g_1, g_2, \dots, g_m)$ 字典序小于序列 $(h_1, h_2, \dots, h_m)$，当且仅当存在下标 $i$（满足 $1 \le i \le m$），使得 $g_i < h_i$，且对所有 $j < i$ 均有 $g_j = h_j$。