记录编号	375994	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]朋友圈	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.985 s
提交时间	2017-02-26 13:24:53	内存使用	60.83 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
 
int A,B,m,ans,a[3010],b[3010];
int x[3010],y[3010],xn,yn,link[3010],E[3010][3010];
char go[3010][3010],g[3010][3010],gb[3010][3010];
bool vis[3010];
 
inline int read(){
	int x=0; char ch;
	while(ch=getchar(),!isdigit(ch));
	while(x=x*10+ch-'0',ch=getchar(),isdigit(ch));
	return x;
}
 
inline int max(int aa,int bb){return aa>bb?aa:bb;}
inline bool jishu(int aa,int bb){
	int k=aa|bb,cnt=0;
	for(int i=1;i<=k;i<<=1)
		if(k&i)
			cnt++;
	return cnt&1;
}
 
bool match(int u){
	for(int i=1;i<=E[u][0];i++){
		int &to=E[u][i];
		if(!vis[to]){
			vis[to]=true;
			if(!link[to]||match(link[to])){
				link[to]=u;
				return true;
			}
		}
	}
	return false;
}
 
inline int zerop(){
	xn=yn=0;
	for(int i=1;i<=B;i++)
		b[i]&1?x[++xn]=i:y[++yn]=i;
	for(int i=1;i<=xn;i++){
		int &now=E[i][0]; now=0;
		for(int j=1;j<=yn;j++)
			gb[x[i]][y[j]]^1?E[i][++now]=j:false;
	}
	int flow=0;
	for(int i=1;i<=xn;i++){
		memset(vis,0,sizeof(vis));
		if(match(i)) flow++;
	}
	return xn+yn-flow;
}
 
inline int onep(){
	int MAX=0;
	for(int j=1;j<=A;j++){
		xn=yn=0;
		for(int i=1;i<=B;i++)
			if(g[j][i])
				b[i]&1?x[++xn]=i:y[++yn]=i;	
		for(int i=1;i<=xn;i++){
			int &now=E[i][0]; now=0;
			for(int j=1;j<=yn;j++)
				gb[x[i]][y[j]]^1?E[i][++now]=j:false;
		}
		int flow=0; 
		for(int i=1;i<=yn;i++) link[i]=0;
		for(int i=1;i<=xn;i++){
			memset(vis,0,sizeof(vis));
			if(match(i)) flow++;
		}
		MAX=max(MAX,xn+yn-flow);
	}
	return MAX+1;
}
 
inline int twop(){
	int MAX=0;
	for(int k=1;k<=A;k++){
		for(int j=k+1;j<=A;j++)
			if((a[k]^a[j])&1){
				xn=yn=0;
				for(int i=1;i<=B;i++)
					if(g[j][i]&&g[k][i])
						b[i]&1?x[++xn]=i:y[++yn]=i;
				for(int i=1;i<=xn;i++){
					int &now=E[i][0]; now=0;
					for(int j=1;j<=yn;j++)
						gb[x[i]][y[j]]^1?E[i][++now]=j:false;
				}
				int flow=0; 
				for(int i=1;i<=yn;i++) link[i]=0;
				for(int i=1;i<=xn;i++){
					memset(vis,0,sizeof(vis));
					if(match(i)) flow++;
				}
				MAX=max(MAX,xn+yn-flow);
			}
	}
	return MAX;
}
 
int main(){
	//freopen("a.txt","r",stdin);
	freopen("friends.in","r",stdin);
	freopen("friends.out","w",stdout);
	int T=read();
	while(T--){
		A=read(); B=read(); m=read();
		for(int i=1;i<=A;i++) a[i]=read();
		for(int i=1;i<=B;i++) b[i]=read();
		for(int i=1;i<=m;i++){
			int xi,yi; scanf("%d%d",&xi,&yi);
			g[xi][yi]=true;
		}
		for(int i=1;i<=B;i++)
			for(int j=i+1;j<=B;j++)
				if(jishu(b[i],b[j]))
					gb[i][j]=gb[j][i]=true;	
		ans=0;
		ans=max(ans,zerop());
		ans=max(ans,onep());
		ans=max(ans,twop());
		printf("%d\n",ans);
	}
	return 0;
}