#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int C,N,K,M,cnt,tot;struct City{	int x,belong;};City cities[5050];int head[2050];int dp[2050][2];bool vis[2050];struct node{	int u,v;	int next;}edge[6500];bool cmp(City a,City b){	if(a.x<b.x) return true;	return false;}int belong[2050];void addedge(int u,int v){	edge[tot].u=u;	edge[tot].v=v;	edge[tot].next=head[u];	head[u]=tot++;}void dfs(int u,int f){	dp[u][0]=0;dp[u][1]=1;	vis[u]=true;	for(int ei=head[u];ei!=-1;ei=edge[ei].next){		if(f!=edge[ei].v&&belong[edge[ei].v]>0&&!vis[edge[ei].v	]){			dfs(edge[ei].v,u);			dp[u][1]+=dp[edge[ei].v][0];			dp[u][0]+=max(dp[edge[ei].v][0],dp[edge[ei].v][1]);		}	}}bool judge(){	int ans=0;	memset(vis,false,sizeof(vis));	for(int i=1;i<=N;i++){		if(!vis[i]&&belong[i]>0){			dfs(i,0);			ans+=max(dp[i][0],dp[i][1]);		}	}	if(ans>=K) return true;	else return false;}int main(){	int T,t=0,u,v,l,r;	scanf("%d",&T);	while(++t<=T){		scanf("%d%d%d%d",&C,&N,&K,&M);		cnt=tot=0;		for(int i=1;i<=C;i++){			scanf("%d%d",&cities[i].x,&cities[i].belong);		}		memset(head,-1,sizeof(head));		sort(cities+1,cities+1+C,cmp);		for(int i=1;i<=M;i++){			scanf("%d%d",&u,&v);			addedge(u,v);			addedge(v,u);		}		cnt=l=r=1;		int ans=-1;		memset(belong,0,sizeof(belong));		while(r<=C){			if(cnt>=K && judge()){			     if(ans==-1||cities[r].x - cities[l].x<ans)    	       	 ans=cities[r].x - cities[l].x;   		         belong[ cities[l].belong ]--;   		         if( belong[ cities[l].belong ]==0 ) cnt--;   		         l++;	       }    	    else{     		      r++;   	    	      belong[ cities[r].belong ]++;      		      if( belong[ cities[r].belong ]==1 ) cnt++;     	   }		}		printf("Case #%d: %d\n",t,ans);	}	return 0;}

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int C = 5005;const int N = 2005;const int M = 1005;int cnt[N]; //i????????int vis[C];int dp[C][2];int c, n, k, m;vector<int>v[N];struct city{    int x, y;    bool operator<(const city &a) const    {        return x<a.x;    }}ct[C];int min(int x, int y){    if(x==-1) return y;    return x<y?x:y;}void dfs(int s){    vis[s] = 1;    dp[s][1] = 1;    dp[s][0] = 0;    for(int i=0; i<v[s].size(); i++)    {        int ss = v[s][i];        if(vis[ss]==1 || cnt[ss]==0) continue;        dfs(ss);        dp[s][1] += dp[ss][0];        dp[s][0] += max(dp[ss][1], dp[ss][0]);    }}bool ok(int l, int r){    int res = 0;    memset(vis, 0, sizeof(vis));    for(int i = l; i<=r; i++)    if(vis[ ct[i].y ]==0)    {        dfs( ct[i].y );        res += max( dp[ ct[i].y ][0], dp[ ct[i].y ][1] );    }    if(res>=k) return true;    else return false;}int solve(){    int kk, l, r;    kk = l = r = 1;    cnt[ ct[1].y ]++;    int ans = -1;    while(r<=c)    {        if(kk>=k && ok(l, r))        {            ans = min(ans, ct[r].x - ct[l].x);            cnt[ ct[l].y ]--;            if( cnt[ ct[l].y ]==0 ) kk--;            l++;        }        else        {            r++;            cnt[ ct[r].y ]++;            if( cnt[ ct[r].y ]==1 ) kk++;        }    }    return ans;}int main(){    int t, tt=0, i, x, y;    scanf("%d", &t);    while(t--)    {        scanf("%d%d%d%d", &c, &n, &k, &m);        for(i=1; i<=n; i++) v[i].clear();        memset(cnt, 0, sizeof(cnt));        memset(vis, 0, sizeof(vis));        for(i=1; i<=c; i++) scanf("%d%d", &ct[i].x, &ct[i].y);        sort(ct+1, ct+1+c);        for(i=1; i<=m; i++)        {            scanf("%d%d", &x, &y);            v[x].push_back(y);            v[y].push_back(x);        }        printf("Case #%d: %d\n", ++tt, solve());    }	return 0;}