Затори на дорогах
У місті N всі дороги двосторонні. Система доріг міста N дозволяє проїхати з кожної точки міста у довільну іншу, але із-за стрімкого збільшення кількості автомобілів постійно виникають затори, проїхати через які за розумний час практично неможливо. Завдяки настійлививм проханням автомобілістів мерія створила інформаційну службу, яка повідомляє автомобілістам про те, як дістатись з однієї точки міста в іншу найкоротшим шляхом, тобто, проїхавши найменш можливе число перехресть, минуючи визникші затори. Напишіть програму, яка дозволить автоматично прокладати цей найкоротший шлях, полегшивши життя як автомобілістам, так і співробітникам служби.
Вхідні дані
У першому рядку через пропуск задано три цілих числа: n, m, k (3 <= n, m <= 1000, 1 <= k <= 50); n – кількість перехресть, m – кількість доріг, k – кількість запитів по розрахунку оптимального маршруту. Нумерація перехресть, доріг та автомобілів починається з одиниці. Наступні m рядків задають список доріг у місті, у кожному рядку пара чисел від 1 до n через пропуск – номера перехресть, з'єднаних дорогою. Далі йде k блоків, кожен з яких описує один запит. Блок починається рядком, що містить три цілих числа, записаних через пропуск: s, f, p (1 <= s, f, p <= m), s, f – номера доріг, які є початковим і кінцевим пунктом руху автомобіля відповідно, p – кількість заторів. У наступних p рядках по одному числу від 1 до m - номери доріг, на яких виникли затори.
Вихідні дані
Вихідний файл містить k блоків, які описують маршрут руху автомобіля з мінімальною кількістю пройдених перехресть. У першому рядку блоку виводиться ціле число – кількість перехресть, через які проходить маршрут. У другому рядку маршрут - послідовність номерів перехресть (цілих чисел від 1 до n) через пропуск. Гарантується, що маршрут з початкового пункту у кінцевий завжди існує.