Traffic Rules
In the capital of a small country, the traffic situation is quite complex. Multi-kilometer traffic jams have essentially brought the city to a standstill, prompting the authorities to implement one-way streets without checking if it's still possible to travel between any two locations without breaking the rules. The city's transportation network consists of N squares connected by M lanes, which may include circular lanes that loop through a square. Each lane allows travel in only one specified direction. On highways, there are lanes for both directions. On a circular lane, movement is restricted to within the square and only in a counterclockwise direction.
The city authorities have installed a video camera on each lane. If Innokenty drives on a prohibited lane (if it exists) or travels in the opposite direction on a one-way street, he will incur a fine of one thousand tugriks for each lane he travels against the rules.
Innokenty, eager to buy discounted ceramic tiles, is determined to reach the store, even if it means breaking the rules. However, he wants to find a route that minimizes the total fine.
Innokenty hasn't yet decided on his starting point or which store he will visit, so he needs to answer several queries of the form: What is the minimum fine to travel from point A to point B? To assist the city's residents, the well-known search engine Index is developing a service to address this need.
Since many of you may eventually interview for a job at this company, show that you can solve this problem.
Input Data
The first line of the input contains two numbers N and M — the number of squares and traffic lanes in the city, respectively (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10000). The following lines describe the lanes where movement is permitted. Each lane is defined by the numbers of two squares it connects, allowing movement from the first square to the second.
The next line contains one number K — the number of queries Innokenty has (1 ≤ K ≤ 10000, N·K ≤ 2·10^7). The subsequent lines describe the queries, each defined by the numbers of two squares between which the cheapest path needs to be found. The path must be from the first square to the second.
Output Data
For each query, output one number — the minimum fine in thousands of tugriks required. If there is no path between the specified pair of squares, output -1.