Пробки на дорогах
В городе 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) через пробел. Гарантируется, что маршрут из начального пункта в конечный всегда существует.