Fortis Fortuna Adiuvat
Your very close friend, John, also known as the Baba Yaga, is often on various missions to complete different tasks. For this, he needs to travel to different countries. For each of his missions, he has a peculiar ritual. Let's say, he is going from country s to country t. He will start his journey from s, visit Continental Hotel, located at country x, and then go to country t. Even if the country t falls on his path from s to x, he will first go to x and then return to t. Consider this as a professional courtesy. To travel from one country to another, he needs to spend a few markers for different favors like mission equipment, food, travel cost, etc. A marker is a small round metal object indicating a debt between two individuals. Markers are witnessed and recognized. That means, if one person offers a marker to another and asks for a favor, the offered person must comply. It is evident from previous statements that these markers are very precious. For this reason, John wants to minimize the number of markers used.
John knows that you're a great programmer. So he has asked you to calculate the number of markers he requires to go on his missions.
Input
Input starts with an integer T (1 ≤ T ≤ 5), the number of test cases.
The first line of each test case contains 4 integers, N (1 ≤ N ≤ 105), the number of countries, M (1 ≤ M ≤ 105), the number of flights connecting them, x (1 ≤ x ≤ N), the location of Continental Hotel and Q (1 ≤ Q ≤ 105), the number of missions John needs to participate in. The countries are conveniently numbered from 1 to N.
The next M lines each will contain three integers u, v and w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 109) indicating that there is a flight from u to v which costs w markers. Then the following Q lines each will contain two integers s (1 ≤ s ≤ N), the country where John currently is in, and t (1 ≤ t ≤ N), the country he needs to go to. There can be multiple flights between two countries.
Output
For each case, print the case number first. Then for all the missions, you have to print the number of markers required in a newline. If such required path from country s to country t doesn't exist, print "Be seeing ya, John" (without the quotation marks).
Sample
| Input | Output |
|---|---|
1 4 4 3 2 1 2 4 1 3 20 2 3 4 3 4 4 1 4 4 1 | Case 1: 12 Be seeing ya, John |
For the first query, John will go through the following sequence of countries: 1 -> 2 -> 3 -> 4. The number of markers required: (4 + 4 + 4) = 12. | |
Dataset is huge, use faster I/O methods.
