Traffic jams
In city N, all roads are two-way. The road network in city N allows travel between any two points, but the rapid increase in the number of cars has led to frequent traffic jams, making it nearly impossible to traverse the city in a reasonable time. In response to persistent requests from motorists, the city hall has established an information service that guides drivers on how to travel from one point to another using the shortest route, minimizing the number of intersections and avoiding traffic jams. Your task is to write a program that automatically determines this shortest path, simplifying the process for both motorists and service staff.
Input
The first line contains three integers separated by spaces: n, m, k (3 <= n, m <= 1000, 1 <= k <= 50); where n is the number of intersections, m is the number of roads, and k is the number of requests for optimal route calculations. Intersections, roads, and cars are numbered starting from one. The next m lines list the roads in the city, with each line containing a pair of numbers from 1 to n separated by a space, representing the intersections connected by a road. Following this, there are k blocks, each detailing one request. Each block starts with a line containing three integers separated by spaces: s, f, p (1 <= s, f, p <= m), where s and f are the roads that mark the starting and ending points of the car's journey, respectively, and p is the number of roads with traffic jams. The next p lines each contain one number from 1 to m, indicating the roads where traffic jams are present.
Output
The output file should contain k blocks, each describing the car's route with the minimum number of intersections. The first line of each block should output an integer representing the number of intersections on the route. The second line should list the route as a sequence of intersection numbers (integers from 1 to n) separated by spaces. It is guaranteed that a route from the starting point to the endpoint always exists.