Codeforces Round 441 (Div. 1, by Moscow Team Olympiad)
C
National Property
Codeforces
2100
原题
← BD →
翻译中…

You all know that the Library of Bookland is the largest library in the world. There are dozens of thousands of books in the library.

翻译中…

Some long and uninteresting story was removed...

翻译中…

The alphabet of Bookland is so large that its letters are denoted by positive integers. Each letter can be small or large, the large version of a letter $*x*$ is denoted by $*x*'$. BSCII encoding, which is used everywhere in Bookland, is made in that way so that large letters are presented in the order of the numbers they are denoted by, and small letters are presented in the order of the numbers they are denoted by, but all large letters are before all small letters. For example, the following conditions hold: $2 < 3$, $2' < 3'$, $3' < 2$.

翻译中…

A word $*x*_{1}, *x*_{2}, ..., *x*_{*a*}$ is not lexicographically greater than $*y*_{1}, *y*_{2}, ..., *y*_{*b*}$ if one of the two following conditions holds:

翻译中…
  • $*a* ≤ *b*$ and $*x*_{1} = *y*_{1}, ..., *x*_{*a*} = *y*_{*a*}$, i.e. the first word is the prefix of the second word;
  • there is a position $1 ≤ *j* ≤ *min*(*a*, *b*)$, such that $*x*_{1} = *y*_{1}, ..., *x*_{*j* - 1} = *y*_{*j* - 1}$ and $*x*_{*j*} < *y*_{*j*}$, i.e. at the first position where the words differ the first word has a smaller letter than the second word has.
翻译中…

For example, the word "$3'$ $7$ $5$" is before the word "$2$ $4'$ $6$" in lexicographical order. It is said that sequence of words is in lexicographical order if each word is not lexicographically greater than the next word in the sequence.

翻译中…

Denis has a sequence of words consisting of small letters only. He wants to change some letters to large (let's call this process a capitalization) in such a way that the sequence of words is in lexicographical order. However, he soon realized that for some reason he can't change a single letter in a single word. He only can choose a letter and change all of its occurrences in all words to large letters. He can perform this operation any number of times with arbitrary letters of Bookland's alphabet.

翻译中…

Help Denis to choose which letters he needs to capitalize (make large) in order to make the sequence of words lexicographically ordered, or determine that it is impossible.

翻译中…

Note that some words can be equal.

翻译中…

Input

翻译中…

The first line contains two integers $*n*$ and $*m*$ ($2 ≤ *n* ≤ 100 000$, $1 ≤ *m* ≤ 100 000$) — the number of words and the number of letters in Bookland's alphabet, respectively. The letters of Bookland's alphabet are denoted by integers from $1$ to $*m*$.

翻译中…

Each of the next $*n*$ lines contains a description of one word in format $*l*_{*i*}, *s*_{*i*, 1}, *s*_{*i*, 2}, ..., *s*_{*i*, *l*_{*i*}}$ ($1 ≤ *l*_{*i*} ≤ 100 000$, $1 ≤ *s*_{*i*, *j*} ≤ *m*$), where $*l*_{*i*}$ is the length of the word, and $*s*_{*i*, *j*}$ is the sequence of letters in the word. The words are given in the order Denis has them in the sequence.

翻译中…

It is guaranteed that the total length of all words is not greater than $100 000$.

翻译中…

Output

翻译中…

In the first line print "Yes" (without quotes), if it is possible to capitalize some set of letters in such a way that the sequence of words becomes lexicographically ordered. Otherwise, print "No" (without quotes).

翻译中…

If the required is possible, in the second line print $*k*$ — the number of letters Denis has to capitalize (make large), and in the third line print $*k*$ distinct integers — these letters. Note that you don't need to minimize the value $*k*$.

翻译中…

You can print the letters in any order. If there are multiple answers, print any of them.

翻译中…

Note

翻译中…

In the first example after Denis makes letters $2$ and $3$ large, the sequence looks like the following:

翻译中…
  • $2'$
  • $1$
  • $1$ $3'$ $2'$
  • $1$ $1$
翻译中…

The condition $2' < 1$ holds, so the first word is not lexicographically larger than the second word. The second word is the prefix of the third word, so the are in lexicographical order. As the first letters of the third and the fourth words are the same, and $3' < 1$, then the third word is not lexicographically larger than the fourth word.

翻译中…

In the second example the words are in lexicographical order from the beginning, so Denis can do nothing.

翻译中…

In the third example there is no set of letters such that if Denis capitalizes them, the sequence becomes lexicographically ordered.

翻译中…

样例

Input #1
4 3
1 2
1 1
3 1 3 2
2 1 1
Output #1
Yes
2
2 3
InputCopy OutputCopy
Input #2
6 5
2 1 2
2 1 2
3 1 2 3
2 1 5
2 4 4
2 4 4
Output #2
Yes
0
InputCopy OutputCopy
Input #3
4 3
4 3 2 2 1
3 1 1 3
3 2 3 3
2 3 1
Output #3
No
InputCopy OutputCopy
题目信息
题号
875C
时间限制
1 s
内存限制
512 MB
标签
2-SAT
DFS 及类似
图论
模拟

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。