#include<bits/stdc++.h>
using namespace std;
typedef int ll;
vector<pair<ll,bool> > aj[300005];
vector<ll> aj2[3005];
bool vis[300005];
ll arr[3005], ma[300005];
ll dp[3005][3002],parent[300005],m,num=1;
void dfs(ll u, ll par,bool a){
	if(a){
		num++;
		aj2[ma[par]].push_back(num);
		ma[u]=num;
		parent[num]=ma[par];
	}else {
		ma[u]=ma[par];
	}
	vis[u]=true;
	arr[ma[u]]++;
	for(ll i=0;i<aj[u].size();i++){
		if(!vis[aj[u][i].first])dfs(aj[u][i].first,u,aj[u][i].second);
	}
}
void solve(ll u,ll c){
	for(ll i=c;i<=m;i++){
		if(c)dp[u][i]=dp[parent[u]][i-1]+arr[u];
		else dp[u][i]=arr[u];
	}
	for(ll i=0;i<aj2[u].size();i++){
		solve(aj2[u][i],c+1);
	}
	for(ll i=0;i<=m;i++)dp[parent[u]][i]=max(dp[parent[u]][i],dp[u][i]);
}
int main(){
	ll n,i,j,k,a,b,c,l,u;

	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>l>>u;
	for(i=0;i<l;i++){
		cin>>a>>b;
		aj[a].push_back(make_pair(b,true));
		aj[b].push_back(make_pair(a,true));
	}
	for(i=0;i<u;i++){
		cin>>a>>b;
		aj[a].push_back(make_pair(b,false));
		aj[b].push_back(make_pair(a,false));
	}
	ma[0]=1;
	dfs(0,0,false);
	parent[1]=1;
	solve(1,0);
	cout<<dp[1][m];
}