English · Original
Chinese · Translation
Formal · Original
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!
## Input
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.
## Output
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.
[samples]
## Note
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_.
现在是125年之后，但人类仍然在逃避一支决心毁灭他们的类人机械种族。或者我们在这里把一些故事搞混了……无论如何，舰队现在规模更小了。然而，在最近的一次升级中，所有导航系统都配备了更高维度的线性代数跳跃处理器。
现在，为了进行一次跳跃，飞船的船长需要指定事件发生所在的 #cf_span[d]-维空间中的一个 _子空间_。她通过提供该子空间的一组生成向量来完成这一操作。
海蒂公主从 #cf_span[m] 艘飞船的船长那里各自收到了这样一组向量。她希望将那些超空间跳跃子空间相同的飞船分组。为此，她希望为每艘飞船分配一个介于 #cf_span[1] 和 #cf_span[m] 之间的组号，使得两艘飞船具有相同的组号，当且仅当它们对应的子空间相等（即使它们是用不同的向量集合给出的）。
帮助海蒂吧！
输入的第一行包含两个用空格分隔的整数 #cf_span[m] 和 #cf_span[d]（#cf_span[2 ≤ m ≤ 30 000]，#cf_span[1 ≤ d ≤ 5]）——分别表示飞船的数量和完整底层向量空间的维度。接下来依次描述 #cf_span[m] 个子空间。第 #cf_span[i] 个子空间对应第 #cf_span[i] 艘飞船，其描述如下：
第一行包含一个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ d]）。随后有 #cf_span[ki] 行，第 #cf_span[j] 行描述第 #cf_span[i] 艘飞船发送的第 #cf_span[j] 个向量。每条 #cf_span[j] 行包含 #cf_span[d] 个用空格分隔的整数 #cf_span[aj]（#cf_span[j = 1, ..., d]），用于描述该向量；满足 #cf_span[|aj| ≤ 250]。第 #cf_span[i] 个子空间是这 #cf_span[ki] 个向量的线性张成。
请输出 #cf_span[m] 个用空格分隔的整数 #cf_span[g1, ..., gm]，其中 #cf_span[gi] 表示分配给第 #cf_span[i] 艘飞船的组号。也就是说，对于任意 #cf_span[1 ≤ i < j ≤ m]，应满足：#cf_span[gi = gj] 当且仅当第 #cf_span[i] 个和第 #cf_span[j] 个子空间相等。此外，序列 #cf_span[(g1, g2, ..., gm)] 应在所有满足该性质的序列中字典序最小。
在样例测试用例中，第一个和最后一个子空间相等，第2至第4个子空间相等，第5至第7个子空间相等。
回忆：两个子空间，一个由向量 #cf_span[v1, ..., vn] 张成，另一个由向量 #cf_span[w1, ..., wk] 张成，当且仅当每个向量 #cf_span[vi] 都可以表示为向量 #cf_span[w1, ..., wk] 的线性组合（即存在系数 #cf_span[α1, ..., αk] 使得 #cf_span[vi = α1w1 + ... + αkwk]），并且每个向量 #cf_span[wi] 也可以表示为向量 #cf_span[v1, ..., vn] 的线性组合时，这两个子空间相等。
回忆：序列 #cf_span[(g1, g2, ..., gm)] 比序列 #cf_span[(h1, h2, ..., hm)] 字典序更小，当且仅当存在一个索引 #cf_span[i]（#cf_span[1 ≤ i ≤ m]），使得 #cf_span[gi < hi]，且对所有 #cf_span[j < i] 都有 #cf_span[gj = hj]。
## Input
输入的第一行包含两个用空格分隔的整数 #cf_span[m] 和 #cf_span[d]（#cf_span[2 ≤ m ≤ 30 000]，#cf_span[1 ≤ d ≤ 5]）——分别表示飞船的数量和完整底层向量空间的维度。接下来依次描述 #cf_span[m] 个子空间。第 #cf_span[i] 个子空间对应第 #cf_span[i] 艘飞船，其描述如下：第一行包含一个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ d]）。随后有 #cf_span[ki] 行，第 #cf_span[j] 行描述第 #cf_span[i] 艘飞船发送的第 #cf_span[j] 个向量。每条 #cf_span[j] 行包含 #cf_span[d] 个用空格分隔的整数 #cf_span[aj]（#cf_span[j = 1, ..., d]），用于描述该向量；满足 #cf_span[|aj| ≤ 250]。第 #cf_span[i] 个子空间是这 #cf_span[ki] 个向量的线性张成。
## Output
请输出 #cf_span[m] 个用空格分隔的整数 #cf_span[g1, ..., gm]，其中 #cf_span[gi] 表示分配给第 #cf_span[i] 艘飞船的组号。也就是说，对于任意 #cf_span[1 ≤ i < j ≤ m]，应满足：#cf_span[gi = gj] 当且仅当第 #cf_span[i] 个和第 #cf_span[j] 个子空间相等。此外，序列 #cf_span[(g1, g2, ..., gm)] 应在所有满足该性质的序列中字典序最小。
[samples]
## Note
在样例测试用例中，第一个和最后一个子空间相等，第2至第4个子空间相等，第5至第7个子空间相等。回忆：两个子空间，一个由向量 #cf_span[v1, ..., vn] 张成，另一个由向量 #cf_span[w1, ..., wk] 张成，当且仅当每个向量 #cf_span[vi] 都可以表示为向量 #cf_span[w1, ..., wk] 的线性组合（即存在系数 #cf_span[α1, ..., αk] 使得 #cf_span[vi = α1w1 + ... + αkwk]），并且每个向量 #cf_span[wi] 也可以表示为向量 #cf_span[v1, ..., vn] 的线性组合时，这两个子空间相等。回忆：序列 #cf_span[(g1, g2, ..., gm)] 比序列 #cf_span[(h1, h2, ..., hm)] 字典序更小，当且仅当存在一个索引 #cf_span[i]（#cf_span[1 ≤ i ≤ m]），使得 #cf_span[gi < hi]，且对所有 #cf_span[j < i] 都有 #cf_span[gj = hj]。
**Definitions**
Let $ m, d \in \mathbb{Z}^+ $ with $ 2 \leq m \leq 30{,}000 $ and $ 1 \leq d \leq 5 $.
For each $ i \in \{1, \dots, m\} $, let $ k_i \in \mathbb{Z}^+ $ with $ 1 \leq k_i \leq d $, and let $ V_i = \text{span}\{ \mathbf{v}_{i,1}, \dots, \mathbf{v}_{i,k_i} \} \subseteq \mathbb{R}^d $, where each $ \mathbf{v}_{i,j} \in \mathbb{Z}^d $ and $ \|\mathbf{v}_{i,j}\|_\infty \leq 250 $.
**Constraints**
1. $ \forall i \in \{1, \dots, m\}, \; k_i \in [1, d] $
2. $ \forall i \in \{1, \dots, m\}, \; \forall j \in \{1, \dots, k_i\}, \; \mathbf{v}_{i,j} \in \mathbb{Z}^d, \; |\mathbf{v}_{i,j}^{(l)}| \leq 250 $ for all $ l \in \{1, \dots, d\} $
**Objective**
Assign a group assignment $ \mathbf{g} = (g_1, \dots, g_m) \in \{1, \dots, m\}^m $ such that:
- $ g_i = g_j \iff V_i = V_j $ for all $ i, j \in \{1, \dots, m\} $,
- $ \mathbf{g} $ is lexicographically minimal among all such assignments.
**Method**
For each $ i \in \{1, \dots, m\} $, compute a canonical basis $ B_i $ for $ V_i $ via Gaussian elimination over $ \mathbb{Q} $, reducing the generating set to a row-echelon form with integer entries normalized to primitive vectors (gcd = 1) and lexicographically ordered.
Let $ C_i $ be the canonical representation of $ V_i $ (e.g., sorted list of basis vectors in reduced row-echelon form).
Group indices $ i $ by $ C_i $, and assign group numbers $ 1, 2, \dots $ in increasing order of the first occurrence of each distinct $ C_i $.
API Response (JSON)
{
"problem": {
"name": "D2. Hyperspace Jump (hard)",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF958D2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "现在是125年之后，但人类仍然在逃避一支决心毁灭他们的类人机械种族。或者我们在这里把一些故事搞混了……无论如何，舰队现在规模更小了。然而，在最近的一次升级中，所有导航系统都配备了更高维度的线性代数跳跃处理器。\n\n现在，为了进行一次跳跃，飞船的船长需要指定事件发生所在的 #cf_span[d]-维空间中的一个 _子空间_。她通过提供该子空间的一组生成向量来完成这一操作。\n\n海蒂公主从 #cf_spa...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ m, d \\in \\mathbb{Z}^+ $ with $ 2 \\leq m \\leq 30{,}000 $ and $ 1 \\leq d \\leq 5 $. \nFor each $ i \\in \\{1, \\dots, m\\} $, let $ k_i \\in \\mathbb{Z}^+ $ with $ 1 \\leq k_i \\leq d $, ...",
"is_translate": false,
"language": "Formal"
}
]
}