← 返回题目列表

Codeforces · 875/C

C. 国有财产

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

你们都知道 Bookland 图书馆是世界上最大的图书馆。图书馆里藏书有几十万册。

一些又长又无趣的故事被删除了......

Bookland 的字母表非常大,其字母都用正整数表示。每个字母可小可大,字母 x 的大版本用 x' 表示。 Bookland 中随处使用的 BSCII 编码就是以这种方式进行的,大字母按照它们所表示的数字的顺序呈现,小字母按照它们所表示的数字的顺序呈现,但所有大字母都在所有小字母之前。例如,以下条件成立:2 < 3、2' < 3'、3' < 2。

如果满足以下两个条件之一,则单词 x1, x2, ..., xa 按字典顺序不大于 y1, y2, ..., yb:

- a ≤ b且x1 = y1, ..., xa = ya,即第一个单词是第二个单词的前缀;
- 有一个位置 1 ≤ j ≤ min(a, b),使得 x1 = y1, ..., xj - 1 = yj - 1 且 xj < yj,即在单词不同的第一个位置第一个单词的字母比第二个单词的字母小。

例如,按字典顺序,单词“3' 7 5”位于单词“2 4' 6”之前。如果每个单词在字典顺序上不大于序列中的下一个单词,则称单词序列按字典顺序排列。

Denis 有一个仅由小写字母组成的单词序列。他想将一些字母改为大写(让我们将此过程称为大写),以使单词序列按字典顺序排列。然而,他很快意识到,由于某种原因,他无法用一个单词来改变一个字母。他只能选择一个字母,并将所有单词中出现的所有字母更改为大字母。他可以使用 Bookland 字母表中的任意字母执行此操作任意次。

帮助 Denis 选择他需要大写(变大)的字母,以使单词序列按字典顺序排序,或者确定这是不可能的。

请注意,某些单词可以相等。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000)——分别是 Bookland 字母表中的单词数和字母数。 Bookland 字母表中的字母由 1 到 m 的整数表示。

接下来的 n 行中的每一行都包含一个单词的描述,格式为 li, si, 1, si, 2, ..., si, li (1 ≤ li ≤ 100 000, 1 ≤ si, j ≤ m),其中 li 是单词的长度,si, j 是单词中字母的序列。这些单词按照丹尼斯在序列中的顺序给出。

保证所有单词的总长度不大于100 000。

输出

如果可以将某些字母大写,从而使单词序列按字典顺序排列,则在第一行中打印“Yes”(不带引号)。否则,打印“否”(不带引号)。

如果需要的话,在第二行中打印 k - Denis 必须大写的字母数量(变大),并在第三行中打印 k 个不同的整数 - 这些字母。请注意,您不需要最小化 k 值。

您可以按任意顺序打印字母。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

Yes
2
2 3

输入 #2

6 5
2 1 2
2 1 2
3 1 2 3
2 1 5
2 4 4
2 4 4

输出 #2

Yes
0

输入 #3

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

输出 #3

No

注意

在 Denis 将字母 2 和 3 变大后的第一个示例中,序列如下所示:

- 2'
- 1
- 1 3' 2'
- 1 1

条件 2' < 1 成立,因此第一个单词按字典顺序不大于第二个单词。第二个单词是第三个单词的前缀,因此按字典顺序排列。由于第三个和第四个单词的第一个字母相同,且 3' < 1,因此按字典顺序,第三个单词不会比第四个单词大。

在第二个示例中,单词从一开始就按字典顺序排列,因此 Denis 无能为力。

在第三个示例中,没有一组字母,如果 Denis 将它们大写,则序列将按字典顺序排列。