Секретна Лабораторія
Відомий агент 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" у першому рядку вихідного файлу. В іншому випадку виведіть мінімальний ризик, який повинен взяти на себе Джеймс, щоб виконати місію.
Після цього виведіть план, якого Джеймс повинен дотримуватися. Спочатку виведіть кількість дослідників, яких потрібно вбити, після чого їх номери. Після цього виведіть час від початку робочого дня, коли Джеймс повинен увійти в лабораторію. Це повинно бути супроводжено списком дверей, через які Джеймс проходить, кожні з часом, коли Джеймс проходить через них, виміряним у секундах від початку робочого дня, коли він входить у лабораторію. Останнє число повинно бути часом, коли місія Джеймса завершується.