Секретная Лаборатория
Знаменитый агент 003 Джеймс Саммер планирует украсть новую супербомбу из секретной лаборатории, расположенной в горах. Лаборатория состоит из нескольких комнат, соединенных дверями. Каждую дверь могут открыть некоторые исследователи, работающие в лаборатории, с помощью своих электронных ключей.
Джеймс может убить некоторых исследователей и забрать их ключи. После этого он сможет открыть все двери, которые могли бы открыть эти исследователи. Также он может просто подождать у двери, пока кто-нибудь не пройдет мимо, и пройти вместе с ним. Агенты изучили распорядок дня в лаборатории, поэтому известно, когда каждый исследователь проходит через двери.
Убивая кого-то, Джеймс увеличивает риск провала своей миссии. Также риск увеличивается с каждой секундой, которую он проводит на территории лаборатории. Поэтому Джеймсу нужно выбрать, чьи ключи ему следует получить, и как добраться до комнаты, где находится супербомба, и выйти, минимизируя риск провала миссии.
Входные данные
Первая строка входного файла содержит n — количество комнат в лаборатории, m — количество дверей и k — количество исследователей (2 ≤ n ≤ 20, 1 ≤ m ≤ 100, 1 ≤ k ≤ 10). Далее следуют m строк с описанием дверей — каждая дверь описывается номерами комнат, которые она соединяет. Все двери двусторонние и могут быть открыты с любой стороны. Две комнаты могут быть соединены более чем одной дверью.
После этого следуют k блоков, описывающих исследователей. Каждый блок начинается с целого числа r_i — риска, который Джеймс принимает, убивая этого исследователя (1 ≤ r_i ≤ 32000). Затем указывается d_i — количество дверей, которые этот исследователь может открыть, за которым следует список дверей. Двери нумеруются, начиная с 1, как они даны в файле. Далее следует распорядок дня исследователя. Он начинается с a_i — количества дверей, которые он открывает ежедневно, за которым следуют a_i пар целых чисел — номер двери, которую открывает исследователь, и время, когда он это делает, измеренное в секундах с начала рабочего дня (это время положительное и не превышает длину рабочего дня, то есть 8 часов или 28800 секунд). События перечислены в хронологическом порядке, a_i ≤ 10. Гарантируется, что каждый исследователь проходит только через те двери, которые он может открыть своим электронным ключом.
Джеймс может начать свою миссию в любое время в течение рабочего дня, и его миссия должна быть завершена до конца рабочего дня. Каждая секунда, которую он проводит в лаборатории, увеличивает его риск на 1. Джеймс входит в лабораторию в холле, который является комнатой номер 1. Супербомба находится в комнате номер n. Джеймс должен добраться до комнаты, где находится супербомба, и вернуться в холл лаборатории. Следует учитывать, что Джеймсу требуется как минимум одна секунда, прежде чем он сможет пройти через две двери, в частности, как минимум одна секунда, прежде чем он сможет пройти через первую дверь. Его миссия заканчивается через одну секунду после того, как он входит в холл лаборатории с супербомбой.
Выходные данные
Если выполнить миссию невозможно, напечатайте "mission impossible" в первой строке выходного файла. В противном случае напечатайте минимальный риск, который Джеймс должен принять для выполнения миссии.
После этого напечатайте план, которому Джеймс должен следовать. Сначала напечатайте количество исследователей, которых нужно убить, за которым следуют их номера. Затем напечатайте время с начала рабочего дня, когда Джеймс должен войти в лабораторию. Это должно быть последовано списком дверей, через которые проходит Джеймс, каждая с указанием времени, когда он проходит через нее, измеренного в секундах с начала рабочего дня, когда он входит в лабораторию. Последнее число должно быть временем, когда миссия Джеймса заканчивается.