| Автор: | VI Всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | exp.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | exp.out |
Сегодня Игорь получил долгожданное разрешение на проведение эксперимента по изучению протекания химических реакций в магнитном поле. При этом используются две установки — генератор магнитного поля и манипулятор, соединяющий реагенты.
Эксперимент разбит на некоторое количество этапов, при этом некоторые из них могут быть выполнены только после завершения определенного набора других этапов. Правда известно, что хотя бы один способ проведения эксперимента существует. На каждом этапе Игорь должен управлять ровно одной из двух установок — либо генератором, либо манипулятором.
Игорь очень дорожит своим временем, и поэтому он хочет провести эксперимент, совершив наименьшее количество перемещений между пультами управления установками. Помогите ему узнать, в каком порядке следует выполнять этапы, чтобы этого добиться.
На первой строке входного файла записано целое число n — количество этапов эксперимента.
Следующие n строк содержат описание этапов. Пронумеруем этапы от 1 до n в некотором произвольном порядке. Тогда i-я из этих строк описывает i-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число ri — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — ri различных целых чисел в диапазоне от 1 до i − 1.
| № | Входной файл (exp.in) |
Выходной файл (exp.out) |
|---|---|---|
| 1 | |
|