← 返回题目列表

Codeforces · 731/D

D. 第80级考古学

中文机器翻译题面 查看原题

考古学家在 Cycleland 金字塔之一的地牢中发现了一个秘密通道。要进入金库,他们必须打开门上一把不寻常的锁。锁由n个单词组成,每个单词由一些象形文字组成。锁附近的墙上有一个圆形开关。该开关的每次旋转都会根据某些规则改变象形文字。附近的说明说,只有当锁上写的单词按字典顺序排序时,门才会打开(字典比较的定义在注释部分给出)。

更改象形文字的规则如下。圆形开关顺时针旋转一圈,将每个象形文字替换为字母表中的下一个象形文字,即,象形文字 x (1 ≤ x ≤ c - 1) 替换为象形文字 (x + 1),象形文字 c 替换为象形文字 1。

帮助考古学家确定他们应该顺时针旋转多少次才能打开门,或者确定这是不可能的,即字母表的循环移位不会使单词序列按字典顺序排序。

输入

输入的第一行包含两个整数 n 和 c (2 ≤ n ≤ 500 000, 1 ≤ c ≤ 106) — 写在锁上的单词数以及不同象形文字的数量。

接下来的 n 行每一行都包含一个单词的描述。其中第 i 行以整数 li (1 ≤ li ≤ 500 000) 开头,表示第 i 个单词的长度,后跟 li 整数 wi, 1, wi, 2, ..., wi, li (1 ≤ wi, j ≤ c) – 组成第 i 个单词的象形文字的索引。索引为 1 的象形文字是字母表中最小的,索引为 c 的象形文字是最大的。

保证所有单词的总长度不超过106。

输出

如果可以通过旋转圆形开关来打开门,请打印整数 x (0 ≤ x ≤ c - 1),它定义了所需的顺时针旋转次数。如果有多个有效的 x,则打印其中任何一个。

如果用这种方法无法开门,则打印 - 1。

示例

输入 #1

4 3
2 3 2
1 1
3 2 3 1
4 2 3 1 2

输出 #1

1

输入 #2

2 5
2 4 2
2 4 2

输出 #2

0

输入 #3

4 4
1 2
1 3
1 4
1 2

输出 #3

-1

注意

如果以下两个条件之一成立,则长度为 m 的单词 a1, a2, ..., am 按字典顺序不大于长度为 k 的单词 b1, b2, ..., bk:

- 在第一个位置 i,使得 ai ≠ bi,字符 ai 在字母表中比字符 bi 更早,即 a 在它们不同的第一个位置具有较小的字符;
- 如果没有这样的位置 i 并且 m ≤ k,即第一个单词是第二个单词的前缀或者两个单词相等。

如果每个单词(最后一个除外)按字典顺序不大于下一个单词,则称单词序列按字典顺序排序。

在第一个示例中,将圆形开关顺时针旋转 1 个位置后,文字如下所示:

在第二个示例中,单词已按字典顺序排序。

在最后一个示例中,可以检查字母表的转换是否有效。