Круизный лайнер не успел отойти от берега и на три мили, как обнаружилось,
что кто-то утопил в бассейне одного из стюардов. Капитан пообещал лично
провести расследование и сбросить подлецов за борт. Группу убийц он хочет
поймать на противоречиях в показаниях, задавая каждому из n пассажиров
лайнера два вопроса:
- Где вы были в момент отплытия?
- Кого вы там видели?
Например, если один пассажир скажет, что был у себя в каюте, а другой
скажет, что видел его возле бассейна, то наверняка кто-то из этих двоих
замешан в убийстве. Но если кто-то не видел человека в том месте, где он
якобы был, капитан не будет считать это противоречием, ведь его могли там
просто не заметить.
Расследование вряд ли будет объективным, ведь злоумышленники сговорилась
между собой, и их показания не будут противоречить друг другу. Честным
же людям скрывать нечего, поэтому они все будут говорить только правду.
Вы вызвались сопоставить нестыковки в ответах пассажиров и выявить группу
подозреваемых. Более того, вы хотите выдать капитану группу с наименьшим
числом пассажиров. Уж раз кому-то суждено сегодня стать кормом для акул,
то пусть пострадает как можно меньше людей.
Исходные данные
В первой строке записано целое число n — количество пассажиров
(2 ≤ n ≤ 400). Далее в n строках записаны показания каждого из пассажиров:
место, где он был в момент отплытия, и список пассажиров, которых он там видел.
Место — непустая строка из строчных латинских букв длиной не более 20.
Список пассажиров, которых видел i-й пассажир, имеет формат m n1 n2 … nm
(0 ≤ m ≤ n − 1; 1 ≤ nj ≤ n; nj ≠ i; 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, Четвертьфинал Восточного подрегиона