print1661. Эксперимент

printЭксперимент

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сегодня Игорь получил долгожданное разрешение на проведение эксперимента по изучению протекания химических реакций в магнитном поле. При этом используются две установки — генератор магнитного поля и манипулятор, соединяющий реагенты.
Эксперимент разбит на некоторое количество этапов, при этом некоторые из них могут быть выполнены только после завершения определенного набора других этапов. Правда известно, что хотя бы один способ проведения эксперимента существует. На каждом этапе Игорь должен управлять ровно одной из двух установок — либо генератором, либо манипулятором.
Игорь очень дорожит своим временем, и поэтому он хочет провести эксперимент, совершив наименьшее количество перемещений между пультами управления установками. Помогите ему узнать, в каком порядке следует выполнять этапы, чтобы этого добиться.
Ввод
На первой строке входного файла записано целое число `n` — количество этапов эксперимента (`1\ ≤\ n\ ≤\ 100`).
Следующие `n` строк содержат описание этапов. Пронумеруем этапы от 1 до `n` в некотором произвольном порядке. Тогда `i`-я из этих строк описывает `i`-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число `r_i` — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — `r_i` различных целых чисел в диапазоне от 1 до `i\ -\ 1`.
Вывод
На первой строке выходного файла выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до `n` — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Пример ввода

3
1 0
0 0
1 2 1 2

Пример вывода

1
2 1 3
Источник: VI Всероссийская командная олимпиада школьников по программированию, 2005
loading