Limits 3s, 512 MB

In Ajobdesh, there are multiple cities and one of them is considered as the capital city. Obviously, King Hulala (the ruler of Ajobdesh) lives in the capital city. Each city is connected with its neighboring cities by single unidirectional roads. You can assume that the cost of traveling every road is equal, and it is considered as single unit.

King Hulala wishes that if anyone wants to go from one city to another city, then he/she must go via capital city. Which means, if anyone wants to go from city u to city v, then he/she needs to go from city u to capital city first. After that, he/she can go from capital city to city v.

Citizens of Ajobdesh are very concerned with their time. So they request the king to build an intelligent system so that they can know the shortest distance for traveling from one city to another one by the new policy declared by the king. Can you help the king?

Input

In the first line, you will be given an integer T (1 ≤ T ≤ 2), denoting the number of test cases.

For each test case, you will be given four integers, N (1 ≤ N ≤ 10000), R (0 ≤ R ≤ min { N(N-1), 10^6 }), C (0 ≤ C < N) and Q (0 ≤ Q ≤ min { N(N-1), 10^6 }) representing the number of cities, the number of roads between the cities, capital city and the number of queries regarding shortest distance between two cities.

The following R lines will contain two city numbers, u and v (0 ≤ u, v < N ; u != v), denoting that anyone can go from city u to city v by using the road.

Then there will be another Q lines, each line will contains two city numbers, u and v, denoting that you need to answer the shortest distance if anyone want to go from city u to city v through the capital city.

Output

For every test case, you need to print "Case T:" (where T is the test case number) in the first line of the output. Then for every query, you need to print the following:

  1. "The shortest distance from u to v is X." (w/o double quotes) if it is possible to travel from u to v through the capital city by shortest distance X.

  2. "Not possible to go from u to v." (w/o double quotes) if it is not possible to travel from u to v.

You need to print every query answer in a separate line.

Sample

InputOutput
1
4 3 1 5
0 1
1 2
2 3
0 1
0 2
0 3
1 2
3 1

Case 1:
The shortest distance from 0 to 1 is 1.
The shortest distance from 0 to 2 is 2.
The shortest distance from 0 to 3 is 3.
The shortest distance from 1 to 2 is 1.
Not possible to go from 3 to 1.

Submit

Login to submit.

Statistics

75% Solution Ratio
UnseenEarliest, Dec '16
Mestu_PaulFastest, 0.0s
Mestu_PaulLightest, 9.4 kB
mumith_fahim99Shortest, 945B
Toph uses cookies. By continuing you agree to our Cookie Policy.