现在已经过去了 125 年,但人类仍然在躲避决心毁灭人类的人形机器人种族。或者也许我们在这里混淆了一些故事......无论如何,舰队现在更小了。然而,在最近的升级中,所有导航系统都配备了更高维的线性代数跳跃处理器。
现在,为了进行跳跃,船长需要指定事件发生所在的 d 维空间的子空间。她通过为该子空间提供一组生成向量来实现这一点。
海蒂公主从m艘船的船长那里收到了这样一套。再次,她希望将超空间跳跃子空间相等的那些飞船分组。为此,她想为每艘船分配一个介于 1 和 m 之间的组号,以便当且仅当它们相应的子空间相等时,两艘船具有相同的组号(即使它们可能使用不同的向量集给出)。
帮助海蒂!
输入
输入的第一行包含两个空格分隔的整数 m 和 d (2 ≤ m ≤ 30 000, 1 ≤ d ≤ 5) – 分别是船舶的数量和完整底层向量空间的维度。接下来依次描述m个子空间。第i个子空间,对应第i艘船,描述如下:
第一行包含一个整数ki (1 ≤ ki ≤ d)。然后是 ki 行,其中第 j 行描述第 i 艘船发送的第 j 个矢量。每 j 行由 d 个空格分隔的整数 aj, j = 1, ..., d 组成,它们描述向量 $$(a_{1},a_{2},\ldots,a_{d})\in\mathbb{R}^{d}$$;它认为 |aj| ≤ 250。第 i 个子空间是这些 ki 向量的线性跨度。
输出
输出 m 个空格分隔的整数 g1, ..., gm,其中 $$g_{i} \in \{1,\ldots,m\}$$ 表示分配给第 i 艘船的组号。也就是说,对于任何 1 ≤ i < j ≤ m,以下应成立:gi = gj 当且仅当第 i 个子空间和第 j 个子空间相等。此外,序列 (g1, g2, ..., gm) 在具有该属性的所有序列中按字典顺序应该是最小的。
示例
输入 #1
8 2 1 5 0 1 0 1 1 0 1 2 0 6 0 1 2 0 1 1 0 2 -5 -5 4 3 2 1 1 0 1 2 1 0 1 0
输出 #1
1 2 2 2 3 3 3 1
注意
在示例测试用例中,第一个和最后一个子空间相等,子空间 2 到 4 相等,子空间 5 到 7 相等。
回想一下两个子空间,一个作为向量 $$v_{1}, \ldots, v_{n} \in \mathbb{R}^{d}$$ 的范围给出,另一个作为向量 $${ w _ { 1 }, \ldots, w _ { k } \in \mathbb { R } ^ { d } }$$ 的范围给出,如果每个子空间都相等向量 vi 可以写成向量 w1, ..., wk 的线性组合(即 \mathbb{R}$$ 中存在系数 $$\alpha_{1}, \ldots, \alpha_{k} \,使得 vi = α1w1 + ... + αkwk),类似地,每个向量 wi 可以写成向量 v1, ..., vn 的线性组合。
回想一下,如果存在索引 i,1 ≤ i ≤ m,则对于所有 j < i,gi < hi 且 gj = hj,则序列 (g1, g2, ..., gm) 按字典顺序小于序列 (h1, h2, ..., hm)。