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

Соревнование школьников. Октябрь 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Бюрократия

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
После того, как открыли чудесные свойства Поля Чудес, в Стране Дураков развился огромный бюрократический аппарат. И теперь, чтобы посадить свою монетку на поле, Буратино должен собрать множество документов. Все усложняется тем, что многие из этих бумаг не дадут без предъявления некоторого набора других.
Так как в Стране Дураков долгое время бушевала безработица, то правительство решило занять максимум населения в бюрократическом аппарате. Поэтому за выдачу одного типа документов отвечает строго один чиновник. Но все эти чиновники за время безработицы уже настолько обленились и разучились работать, что соглашаются выдавать документы только по одному дню в неделю. Не удивительно, что очереди становились такими, что нужно было простоять целый день у одного кабинета, чтобы получить бумагу, и после этого совсем не оставалось времени, чтобы получить ещё что-то в этот же день.
Естественно, что Буратино хочет получить прибыль от своих вложений как можно быстрее, поэтому он решил получить необходимый набор документов как можно быстрее. Для этого он обошел приёмные всех чиновников и занумеровал их от 1 до N включительно. А также записал для каждого кабинета номер приёмного дня недели и набор номеров тех чиновников, от которых нужно получить бумаги, прежде чем идти на приём.
Подумав некоторое время, Буратино так и не смог найти оптимального решения своей задачи. И тогда он пообещал половину будущей прибыли тому, кто сможет помочь ему в этом.

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

В первой строке записано количество чиновников в Стране Дураков N (1 ≤ N ≤ 100) и количество дней в неделе по календарю Страны Дураков L (1 ≤ L ≤ 100). В следующей строке перечислены номера приёмных дней чиновников Ai (1 ≤ AiL). Далее N строк описывают наборы документов, необходимых для получения соотв. документа. Набор документов состоит из чисел, разделённых пробелами. Известно, что в i-й строке нет документа с номером i. Каждая строка завершается 0, что означает конец набора. Если набор пустой, то документ можно получить, ничего дополнительно не предъявляя. После этих строк содержится одно число — текущий день недели K (1 ≤ KL). В следующей строке содержится список уже имеющихся у Буратино документов на текущий день. Список состоит из чисел, разделённых пробелами, и завершается 0. Затем в таком же формате дан список документов, которые требуется получить.
Хоть Страна Дураков и имеет такой, казалось бы, идеальный источник дохода, но из-за созданной волокиты и государство не может получить огромную часть, причитающихся ему налогов. В результате денег хватило только на содержание одного офиса, а, значит, не может работать больше одного чиновника одновременно.

Результат

В случае если невозможно получить необходимый набор документов, выведите «No Solution». Иначе выведите минимальное количество дней, не считая текущий, которое уйдёт для получения всего набора, и в следующей строке перечислите в хронологическом порядке все получаемые документы через пробел. Если есть несколько вариантов ответа с одинаковым минимальным временем, то можно вывести любой из них.

Пример

исходные данныерезультат
2 7
1 2
0
1 0
1
1 0
2 0
1
2
Автор задачи: Анатолий Углов, Евгений Крохалев
Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1337. Бюрократия