Dereck lives in a city consisting of houses number from
to
. These
houses are connected by
two-way roads.
Dereck is a very busy person. He has errands to run for his master, Derek. For each errand, he picks something up from house
and must deliver it to house
. However, Derek is suspicious that Dereck is not taking the shortest path from
to
. Thus, Derek wants Dereck to go through house
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 for each errand may result in Dereck not taking the shortest path from house
to
. Thus, Derek wants Dereck to take the shortest path from
to
, and then the shortest path from
to
.
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,
, 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 lines will each contain two integers,
, meaning that house
and house
are connected by a single road of length
. Note that there may be more than one road between any two neighbourhoods.
The next lines will each contain two integers,
, meaning that Dereck picks something up at
and must deliver it to
.
Output Specification
For each errand, print the shortest path from house to house
for Dereck, under the constraint that he must pass through house
. If it is impossible, print
This is a scam!
.
Constraints
Subtask 1 [5%]
Subtask 2 [25%]
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.