Задача C. Эксперимент

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:exp.in   Ограничение памяти:64 Мб
Выходной файл:exp.out  

Условие

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

Эксперимент разбит на некоторое количество этапов, при этом некоторые из них могут быть выполнены только после завершения определенного набора других этапов. Правда известно, что хотя бы один способ проведения эксперимента существует. На каждом этапе Игорь должен управлять ровно одной из двух установок — либо генератором, либо манипулятором.

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

Формат входного файла

На первой строке входного файла записано целое число n — количество этапов эксперимента.

Следующие n строк содержат описание этапов. Пронумеруем этапы от 1 до n в некотором произвольном порядке. Тогда i-я из этих строк описывает i-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число ri — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — ri различных целых чисел в диапазоне от 1 до i − 1.

Формат выходного файла

На первой строке выходного файла выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до n — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Ограничения

1 ≤ n ≤ 100

Примеры тестов

Входной файл (exp.in) Выходной файл (exp.out)
1
3
1 0
0 0
1 2 1 2
1
2 1 3

0.034s 0.008s 15