Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fortis Fortuna Adiuvat

By ishtupeed · Limits 1s, 256 MB

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

InputOutput
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.
For the second query, there is no path from country 4 to country 1.


Dataset is huge, use faster I/O methods.


Discussion
Statistics

75% Solution Ratio

Wojciech.324122Earliest, 1w ago

sakibalaminFastest, 0.1s

yead_025Lightest, 22 MB

kzvd4729Shortest, 1326B

Submit

Login to submit