代码中注释的那一段代表A中选一个的情况，把他注释掉就能过，不注释就过不去，wa on#1,

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=3205;
int t; 
int n,m,nm;
int a[N],b[N];
bool e[N+N][N+N];
vector<int>g[N];
int vis[N],num,flag[N],tot;
int p[N];
bool match(int x){
	for(int i:g[x]){
		if(vis[i]!=num&&flag[i]==tot){
			vis[i]=num;
			if(!p[i]||match(p[i])){
				p[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
signed main(){
	read(t);
	read(n);read(m);read(nm);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=m;i++)read(b[i]);
	for(int i=1;i<=m;i++){
//		if(b[i]&1)
		for(int j=i+1;j<=m;j++){
//			cout<<i<<' '<<j<<"abs"<<endl;
//			cout<<(b[i]^b[j])%2<<' '<<(__builtin_popcount((b[i]|b[j]))&1)<<endl;
			if(((b[i]^b[j])&1)==0&&((__builtin_popcount((b[i]|b[j])))&1)==0){
//				cout<<i<<"->"<<j<<endl;
				g[i].push_back(j);g[j].push_back(i);
			}
		} 
	}
	for(int u,v,i=1;i<=nm;i++){
		read(u);read(v);
		e[u][v+N]=e[v+N][u]=1;
	}
	int ans=0;int maxx=0;
	for(int i=1;i<=m;i++){
		num++;
		if(b[i]&1)
		ans+=match(i);
	}
	maxx=m-ans;
	
//	for(int i=1;i<=n;i++){
//		memset(p,0,sizeof(p));
//		tot++;
//		int ch=0;
//		ans=0;
//		for(int j=1;j<=m;j++){
//			if(e[i][j+N]){
//				flag[j]=tot;
//				ch++;
//			}
//		}
//		for(int j=1;j<=m;j++){
//			if(flag[j]==tot&&(b[j]&1)){
//				num++;
//				ans+=match(j);
//			}
//		}
//		maxx=max(maxx,1+ch-ans);
//	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if((a[i]^a[j])%2==0)continue;
			tot++;
			memset(p,0,sizeof(p));
			int ch=0;
			ans=0;
			for(int k=1;k<=m;k++){
				if(e[i][k+N]&&e[j][k+N]){
					flag[k]=tot;ch++;
				}
			}
			for(int k=1;k<=m;k++){
				if(flag[k]==tot&&(b[k]&1)){
					num++;
					ans+=match(k); 
				}
			}
			maxx=max(maxx,2+ch-ans);
//			cout<<2+ch-ans<<endl;
		}
	}
	cout<<maxx;
	return 0;
}