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