Тема #140877

Долбаный паскаль

Задача D. Доказательство теоремы
(Время: 1 сек. Память: 16 Мб Баллы: 100)

Преподаватель читает курс лекций, в рамках которого обычно доказывается N различных теорем. Некоторые теоремы могут ссылаться в доказательстве друг на друга. Более точно, каждая теорема Ti зависит от некоторого набора из Ci других теорем; доказать ее можно лишь доказав не менее половины теорем из данного набора. При этом структура курса такова, что нет такой теоремы, от которой зависели бы две или более различных теоремы, а также нет цепочки теорем (Ti1,Ti2, . . . , Tis) такой, что Ti1 зависит от Ti2, Ti2 зависит от Ti3, …, Tis−1 зависит от Tis, а Tis – от Ti1.

Однако, в этом семестре в связи с обилием праздников, перекрывающихся с лекциями, может не удаться доказать все теоремы курса. Тем не менее, нужно доказать основную теорему курса – это центральный результат всей теории, и именно его, скорее всего, придется применять слушателям в других курсах в следующем семестре. Поэтому преподаватель хочет расположить теоремы в таком порядке, чтобы основную теорему курса удалось доказать как можно раньше. Затем, если останется время, он сможет вернуться к доказательству других, менее важных теорем.

Для простоты будем считать, что все теоремы доказываются за одинаковое время. Нужно доказать такое множество теорем и в таком порядке, чтобы основная теорема оказалась доказанной и чтобы общее время доказательства было минимально.
Входные данные

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10 000) – количество теорем. Каждая из следующих N строк описывает теоремы, от которых зависит Ti−1, где i – номер этой строки во входном файле. Эти строки имеют вид Ai,1 Ai,2 ... Ai,Ci 0; здесь Ai,j – номер теоремы, от которой зависит Ti−1. Среди всех чисел Ai,j во входном файле нет двух одинаковых. Основная теорема имеет номер 1. Все числа во входном файле целые.
Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите K – минимальное количество теорем, которые потребуется доказать. В последующих K строках выведите номера этих теорем в порядке их доказательства, по одному числу в каждой. Если ответов с максимальным K несколько, можно вывести любой из них.