CF731D 80-th Level Archeology

考古学家们在 Cycleland 金字塔的地牢内发现了一条密道。要进入金库，他们需要打开门上的一道特殊锁。这把锁由 $n$ 个单词组成，每个单词由若干个象形文字组成。锁边的墙上有一个圆形开关。每转动该开关一次，象形文字会按照某种规则变化。旁边的说明说，只有当锁上的单词按字典序排列时，门才会打开（字典序比较的定义见提示部分）。 象形文字的变化规则如下：每顺时针转动一次开关后，每个象形文字会被替换为字母表中的下一个象形文字，即象形文字 $x$（$1 \leq x \leq c-1$）会被替换为 $x+1$，而象形文字 $c$ 会被替换为 $1$。 请帮助考古学家们确定需要顺时针旋转多少次开关才能打开大门，或者判断是否无法做到，即无论字母表如何环状偏移，单词序列都无法按字典序排列。

输入的第一行包含两个整数 $n$ 和 $c$（$2 \leq n \leq 500\,000$，$1 \leq c \leq 10^6$）——写在锁上的单词数和不同象形文字的数量。 接下来的 $n$ 行，每行为一个单词的描述。第 $i$ 行以一个整数 $l_i$（$1 \leq l_i \leq 500\,000$）开头，表示第 $i$ 个单词的长度，后跟 $l_i$ 个整数 $w_{i,1}$，$w_{i,2}$，...，$w_{i,l_i}$（$1 \leq w_{i,j} \leq c$）——组成该单词的象形文字编号。象形文字编号 $1$ 在字母表中最小，$c$ 最大。 保证所有单词的总长度不超过 $10^6$。

如果可以通过转动开关打开大门，输出一个整数 $x$（$0 \leq x \leq c-1$），表示所需的顺时针转动次数。如果有多个答案，输出任意一个均可。 如果无法通过这种方法打开大门，输出 $-1$。

长度为 $m$ 的单词 $a_1, a_2, \dots, a_m$ 字典序不大于长度为 $k$ 的单词 $b_1, b_2, \dots, b_k$，当且仅当： - 存在第一个位置 $i$，使得 $a_i \neq b_i$，且 $a_i$ 在字母表中排列早于 $b_i$（即 $a$ 在第一个不同位拥有更小的字符）； - 如果没有这样的 $i$，且 $m \leq k$，即第一个单词是第二个单词的前缀，或两单词完全相等。 若整个单词序列满足每个单词（除了最后一个）都字典序不大于下一个单词，则称为按字典序排列。 在第一个样例中，顺时针转动开关 $1$ 次后，单词变为： `

1 3

2

3 1 2

3 1 2 3

` 在第二个样例中，单词原本就已按字典序排列。 最后一个样例，可以验证无论如何偏移字母表都无法满足条件。 由 ChatGPT 5 翻译