#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define captype int

const int MAXN = 100010;   //点的总数
const int MAXM = 4000100;    //边的总数
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
}edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];
int dis[MAXN];
int cur[MAXN];
int pre[MAXN];

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int s,int t,int n){
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[s]=-1;
    gap[0]=n;

    captype ans=0;
    int u=s;
    while(dis[s]<n){
        if(u==t){
            captype mint=INF;
            int id;
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])
            if(mint>edg[i].cap-edg[i].flow){
                mint=edg[i].cap-edg[i].flow;
                id=i;
            }
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
                edg[i].flow+=mint;
                edg[i^1].flow-=mint;
            }
            ans+=mint;
            u=edg[id^1].to;
            continue;
        }
        bool flag=0;
        for(int i=cur[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap>edg[i].flow&&dis[u]==dis[edg[i].to]+1){
            cur[u]=pre[edg[i].to]=i;
            flag=true;
            break;
        }
        if(flag){
            u=edg[cur[u]].to;
            continue;
        }
        int minh=n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap>edg[i].flow && minh>dis[edg[i].to]){
            cur[u]=i; minh=dis[edg[i].to];
        }
        gap[dis[u]]--;
        if(!gap[dis[u]]) return ans;
        dis[u]=minh+1;
        gap[dis[u]]++;
        if(u!=s)
         u=edg[pre[u]^1].to;
    }
    return ans;
}

int fath[MAXN];
int findroot(int x){
    if(x!=fath[x])
     fath[x]=findroot(fath[x]);
     return fath[x];
}
void setroot(int x,int y){
    x=findroot(x);
    y=findroot(y);
    fath[x]=y;
}
void rebuildMap(int mapt[255][255],int n){//处理朋友之间的关系
    int mp[255][255]={0};
    for(int i=1; i<=n; i++)
    fath[i]=findroot(i);
    for(int i=1; i<=n; i++){
        int j=fath[i];
        for(int e=1; e<=n; e++)
        mp[j][e]|=mapt[i][e];
    }
    for(int i=1; i<=n; i++){
        int j=fath[i];
        for(int e=1; e<=n; e++)
        mapt[i][e]=mp[j][e];
    }
}
int main()
{
    int T,n,m,k,f,mapt[255][255];
    int u,v;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&n,&m,&k,&f);

        init();
        memset(mapt,0,sizeof(mapt));
        for(int i=1; i<=n; i++)
            fath[i]=i;

        while(m--){
            scanf("%d%d",&u,&v);
            mapt[u][v]=1;
        }
        while(f--){
            scanf("%d%d",&u,&v);
            setroot(u,v);
        }
        rebuildMap(mapt,n);

        int s=0, t=3*n+1;
        for(int i=1; i<=n; i++){
            addEdg(s,i,0);
            addEdg(i,i+n,k);
            for(int j=1; j<=n; j++)
            if(mapt[i][j])
                addEdg(i,j+2*n,1);
            else
                addEdg(i+n,j+2*n,1);

            addEdg(i+2*n,t,0);
        }
        
        int ans=0 , l=0 , r=n ,mid;
        while(l<=r){
            mid=(l+r)>>1;
            
            for(int i=0; i<eid; i++)
                edg[i].flow=0;
            for(int i=head[s]; i!=-1; i=edg[i].next)
                edg[i].cap=mid;
            for(int i=head[t]; i!=-1; i=edg[i].next)
                edg[i^1].cap=mid;
                
            if(n*mid==maxFlow_sap(s,t,t+1))
                ans=mid,l=mid+1;
            else
                r=mid-1;
        }
        
        printf("%d
",ans);
    }
}