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.
Input Specification
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~.
Output Specification
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!.
Constraints
Subtask 1 [5%]
~N, M, Q \le 100~
Subtask 2 [25%]
~C = 1~
Subtask 3 [70%]
No additional constraints.
Sample Input
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
Sample Output
1
2
This is a scam!
This is a scam!
Comments
I'm only running one BFS yet I'm still TLE... Can someone help me?
Use an ArrayList instead of a HashMap for adjacency list. It's much faster.