Dereck lives in a city consisting of ~N~ houses number from ~1~ to ~N~. These ~N~ houses are connected by ~M~ two-way roads.
Dereck is a very busy person. He has ~Q~ errands to run for his master, Derek. For each errand, he picks something up from house ~a~ and must deliver it to house ~b~. However, Derek is suspicious that Dereck is not taking the shortest path from ~a~ to ~b~. Thus, Derek wants Dereck to go through house ~C~ for each errand, so that Derek can make sure that Dereck is taking the shortest path.
Derek, being the very smart person he is, knows that going through house ~C~ for each errand may result in Dereck not taking the shortest path from house ~a~ to ~b~. Thus, Derek wants Dereck to take the shortest path from ~a~ to ~C~, and then the shortest path from ~C~ to ~b~.
Dereck, not being very good at finding the shortest path, wants you to help him find the shortest path for each errand.
The first line will contain four integers, ~N, M, Q, C~ ~(1 \le N \le 10^5, 1 \le M \le 2 \times 10^5, 1 \le Q \le 10^5, 1 \le C \le N)~, which represents the number of houses, the number of roads, the number of errands, and the house that Dereck must go through for each errand, respectively.
The next ~M~ lines will each contain two integers, ~u, v~ ~(1 \le u, v \le N)~, meaning that house ~u~ and house ~v~ are connected by a single road of length ~1~. Note that there may be more than one road between any two neighbourhoods.
The next ~Q~ lines will each contain two integers, ~a, b~ ~(1 \le a, b \le N)~, meaning that Dereck picks something up at ~a~ and must deliver it to ~b~.
For each errand, print the shortest path from house ~a~ to house ~b~ for Dereck, under the constraint that he must pass through house ~C~. If it is impossible, print
This is a scam!.
Subtask 1 [5%]
~N, M, Q \le 100~
Subtask 2 [25%]
~C = 1~
Subtask 3 [70%]
No additional constraints.
6 7 4 1 1 2 1 3 1 4 2 3 3 4 6 5 5 5 1 4 3 4 5 6 5 5
1 2 This is a scam! This is a scam!