위키백과 언어

내가 ``단어 [zebra, anka, duva]을 정렬해!''라고 말하면, 여러분은 재빨리 [anka, duva, zebra]이라고 답할 것이다. 쉽지 않은가? 단어의 뜻이나 그 언어의 모든 문자를 알지 못하더라도 마찬가지다. 예를 들면 [fünf, como estás, désolé] 같은 경우다. 우리는 스웨덴어와 영어를 알고 있으므로 답이 아마 [como estás, désolé, fünf]일 것임을 안다. 아직은 그리 어렵지 않다. 하지만 단어 목록에 중국 문자, 페르시아 문자 및 그 밖의 비라틴 문자가 포함되기 시작하면, 그러한 단어 목록을 정렬할 수 있는 프로그래밍 올림피아드 참가자는 아마 거의 없을 것이다. 영어 단어와 페르시아어 단어를 어떻게 비교하겠는가? 문제 출제자 중 한 명은 페르시아어 단어를 어떻게 발음하는지 알고 있지만, 그런 지식이 없다면 어려워진다.

이제 정렬된 단어 목록을 만들고 싶다고 가정하자. 이를 위해 각자 몇몇 단어를 알아보고 그 단어들 사이의 순서를 아는 여러 사람이 있다. 단어 목록에 모든 단어를 포함할 필요는 없지만, 포함하는 단어들이 올바르게 정렬되어 있다고 완전히 확신할 수 있어야 한다. 단어 목록에 포함할 수 있는 단어 수의 최댓값을 계산하고, 그 수만큼의 단어를 포함하는 유효한 단어 목록을 출력하는 프로그램을 작성하라.

점수

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$30$| $N \leq 30$

$2$ |$70$| 추가 제한 없음.

편의를 위해 단어 자체를 입력받지 않으며, 대신 각 단어는 $0$에서 $N-1$ 사이의 인덱스로 표현된다. 입력의 첫째 줄에는 두 정수 $N$ ($1 \leq N \leq 130000$)과 $P$ ($1 \leq P \leq 10^5$)이 주어지며, 여기서 $N$은 단어의 수이고 $P$은 사람의 수이다. 그다음에는 $P$개의 줄이 주어지며, 각 줄은 특정한 한 사람이 아는 단어들의 순서를 나타낸다. 각 줄은 해당 사람이 상대적인 정렬 순서를 아는 단어의 수를 나타내는 정수 $2 \leq p_i \leq 25$으로 시작한다. 이어서 $p_i$개의 정수가 주어지는데, 이들은 $0$에서 $N-1$ 사이에 있는 그 사람이 아는 단어들의 인덱스이며, 정렬되어야 하는 순서대로 나열된다. $N$개의 단어가 모두 어떤 목록에든 등장한다고 보장되지 않으며, 한 단어가 여러 목록에 등장할 수도 있다. 입력에는 모순이 없다.

먼저 정수 하나를 출력한다. 이는 올바르게 정렬되었다고 보장되는 단어 목록에 포함할 수 있는 단어의 최대 개수 $M$이다. 그다음 그러한 정렬된 단어 목록 하나를, $M$개의 단어 인덱스를 포함하는 한 줄로 출력한다. 가능한 단어 목록이 여러 개라면 그중 아무 것이나 출력해도 된다.