Traffic jams#171
In city N, all roads are two-way. The road network in city N allows travel between any two intersections, but the rapid increase in the number of cars has led to frequent traffic jams, making it nearly impossible to travel through the city in a reasonable time. In response to persistent requests from motorists, the city hall has established an information service that informs drivers how to get from one intersection to another using the shortest route, i.e., traversing the minimum possible number of intersections while avoiding traffic jams. Your task is to write a program that automatically finds such a shortest path, making life easier for motorists and service staff.
The first line contains three integers separated by spaces: , , (3 \leq n, m \leq 1000, 1 \leq k \leq 50), where is the number of intersections, is the number of roads, and is the number of optimal route queries. Intersections, roads, and cars are numbered starting from . The next lines describe the roads in the city; each line contains a pair of numbers from to separated by a space — the numbers of the intersections connected by a road.
After this, there are blocks, each describing a query. Each block starts with a line containing three integers separated by spaces: , , (1 \leq s, f, p \leq m), where and are the numbers of roads at the starting and final points of the car's journey, respectively, and is the number of jammed roads. The next lines contain the numbers of the roads ( to ) where traffic jams have occurred.
The output should contain blocks, each describing the shortest route (minimum number of intersections traversed). The first line of each block must contain an integer indicating the number of intersections in the route. The second line must provide the route as a sequence of intersection numbers (integers from to ) separated by spaces. A route from the starting point to the endpoint is guaranteed to exist.
Example 1