ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2017. Меньшее из зол

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Круизный лайнер не успел отойти от берега и на три мили, как обнаружилось, что кто-то утопил в бассейне одного из стюардов. Капитан пообещал лично провести расследование и сбросить подлецов за борт. Группу убийц он хочет поймать на противоречиях в показаниях, задавая каждому из n пассажиров лайнера два вопроса:
  1. Где вы были в момент отплытия?
  2. Кого вы там видели?
Например, если один пассажир скажет, что был у себя в каюте, а другой скажет, что видел его возле бассейна, то наверняка кто-то из этих двоих замешан в убийстве. Но если кто-то не видел человека в том месте, где он якобы был, капитан не будет считать это противоречием, ведь его могли там просто не заметить.
Расследование вряд ли будет объективным, ведь злоумышленники сговорилась между собой, и их показания не будут противоречить друг другу. Честным же людям скрывать нечего, поэтому они все будут говорить только правду. Вы вызвались сопоставить нестыковки в ответах пассажиров и выявить группу подозреваемых. Более того, вы хотите выдать капитану группу с наименьшим числом пассажиров. Уж раз кому-то суждено сегодня стать кормом для акул, то пусть пострадает как можно меньше людей.

Исходные данные

В первой строке записано целое число n — количество пассажиров (2 ≤ n ≤ 400). Далее в n строках записаны показания каждого из пассажиров: место, где он был в момент отплытия, и список пассажиров, которых он там видел. Место — непустая строка из строчных латинских букв длиной не более 20. Список пассажиров, которых видел i-й пассажир, имеет формат m n1 n2 … nm (0 ≤ mn − 1; 1 ≤ njn; nji; nj < nj+1).

Результат

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

Примеры

исходные данныерезультат
3
bar 0
bar 1 1
pool 2 1 2
1
3
3
pool 2 2 3
pool 2 1 3
pool 2 1 2
1
1

Замечания

В первом примере возможно, что первый и второй пассажиры — убийцы, а третий говорит правду. А возможно, что первые двое говорят правду, а третий — убийца. Нужно вывести второй вариант, так как в нём группа подозреваемых имеет меньший размер.
Во втором примере все три пассажира не противоречат друг другу, и убийцей может быть любой из них.
Автор задачи: Олег Долгоруков
Источник задачи: NEERC 2014, Четвертьфинал Восточного подрегиона