Description

Lawrence is a traveling merchant that travels between towns of numerous countries, trading various goods like wheat, pelts, salt, coins, and armor (with a lovely company, that is).

However, there is a small problem. Some of these countries are hostile against each other, and would forbid any personnel that started their trip from a hostile country to enter any town of their own.

For example, if the countries Trenni and Ploania are hostile against each other, with Pasloe being a town of Trenni and Enberch being a town of Ploania. It would not be possible for any traveler starting their trip from Pasloe to either go to Enberch or stop by Enberch in the middle of their trip.

Accordingly, Lawrence would need to plan detours for his trips so as to bypass hostile towns. At the same time, Lawrence would also want to minimize his travel distance for any trip he made.

You are to write a C/C++ program that could help Lawrence find the shortest distance from one town to another.
Your program should take in country and town information, country hostility information, town-town distances, and finally queries for shortest distance from one town to another.

Your program MAY use C++ standard library headers.

Input

A new line containing

• The number of country-town pairs (M, 0 < M <= 100)
• The number of mutual hostile country pairs (N, 0 <= N)
• The number of roads between town pairs (P, 0 <= P)
• The number of shortest path distance queries to be answered (Q, 0 < Q).

Then followed by M lines of country-town pairs, in the format of COUNTRY_ID TOWN_ID per line.
Then followed by N lines of mutual hostility country pairs, in the format of COUNTRY1_ID COUNTRY2_ID per line.
Then followed by P lines of roads between town pairs, in the format of TOWN1_ID TOWN2_ID DIST per line.
Finally, then Q lines of path distance queries, in the format of START_TOWN_ID END_TOWN_ID per line.

Constraints

• The town and country IDs are positive integers, each storable in an int variable.
• Each town belongs to one, and only one country.
• The county and town IDs in mutual hostility country pairs, road pairs, and path distance queries will be valid (i.e., there will be a country-town pair describing the country and town).
• For each road, 0 < DIST <= 10000.
• For each query, START_TOWN_ID != END_TOWN_ID.

Output

Output the distances for the distance queries, one per line.

Note if there is no path (including the cases where there are only paths that go through hostile towns), you should output a distance of -1.

Sample Input  Download

Sample Output  Download

Discuss