Missile

Long long ago,there is a strange area where all the C cities are located in a straight line.To make things easy,lets regard the line as X axis.
Even more strangely,cities belonging to the same country are not necessarily adjacent to each other.
But people of these countries are still living happily with their friends.
However,their enemies are preparing for a disastrous attack.Recently they have invented a new weapon called missile,which can destroy any city if they have enough power.If they want to destroy a set of cities,the power required is max{xi}-min{xj},where i and j are all from the city set they want to destroy.Now the enenies are wondering the minimum power needed to destroy some cities which are from at least K different countries.This is an easy task.The problem is that some countries are strangely protected.That means ,if country A and country B has a special relationship,you can destroy at most one country's cities.A good news is that the relationships will not form circles.But the enemies regard it as helpless,so they order you to write a programme to calculate the specific power.In this task,you can assume that once the missile is launched with certain power,it will destroy the cities from as more countries as possible.

There is an integer T (1<=T<=60) indicating the cases you have to solve.Then the following T cases,each one begins with four integers C,N,K,M.C is the number of cities.N is the number of different countries.K is the number of distinct countries the enemies want to destroy.M is the number of the strange relationships. Then comes the next C lines,each line has two integers.The first one is the city's position x(-10⁹<=x<=10⁹),and the second one is the country Y it belongs to(1<=Y<=N).
No two cities are located in the same position.In last M lines, each line contains two integers A and B (1 <= A, B <= N) which means country A and country B has a special relationship.(1<=C<=5000,1<=N<=2000,1<=K<=N,0<=M<=1000)

First you should output "Case #X:" ,without quote.X means the case number you are dealing with.After that ,you should output a blank and the answer.If it's impossible,then the answer should be -1.See sample for more details.

2
3 3 2 1
0 1
2 2
5 3
1 2

3 3 3 1
0 1
2 2
5 3
1 2

Case #1: 3
Case #2: -1

Not all the cases are big ones.

1guangnian@UESTC03

2012 Multi-University Training Contest 6