## GlobeX Cup '18 J5 - Errands

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

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!.

#### 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!