#include <bits/stdc++.h>
using namespace std;
const int N=5e2+7;
int n,m,k,f,ans;
int s[N][N],len[N];
int fa[N],a[N],b[N];
int find(int k){return (k==fa[k])?(k):(fa[k]=find(fa[k]));}
int main(void)
{
	scanf("%d%d%d%d",&n,&m,&k,&f);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)	{
		scanf("%d%d",a+i,b+i);
		b[i]+=n;
	}
	for(int i=1;i<=f;i++)	{
		int c,d;
		scanf("%d%d",&c,&d);
		fa[find(c)]=find(d);
	}
	for(int i=1;i<=m;i++)
		s[find(a[i])][++len[find(a[i])]]=b[i];
	for(int i=1;i<=n;i++)	{
		sort(s[i]+1,s[i]+len[i]+1);
		len[i]=unique(s[i]+1,s[i]+len[i]+1)-s[i]-1;
	}
	ans=1<<30;
	for(int i=1;i<=n;i++)
		ans=min(len[find(i)],ans);
	printf("%d\n",ans+k>n?n:ans+k);
	return 0;
}