eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Затори на дорогах

Затори на дорогах

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

У місті 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) через пропуск. Гарантується, що маршрут з початкового пункту у кінцевий завжди існує.

Приклад

Вхідні дані #1
7 8 2
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 5
7 4 1
8
1 5 1
2
Вихідні дані #1
3
7 6 5
2
1 5