记录编号	375772	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]朋友圈	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.169 s
提交时间	2017-02-25 20:13:58	内存使用	85.28 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=3010,Edge=1e7+10;
int A,B,M,a[N],b[N];
bool check(int x){
	int ans=0;
	for (;x;x-=x&-x) ans++;
	return ans&1;
}
int head[N],next[Edge],cnt,w[Edge],flow;
void add(int f,int t){
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int match[N],vis[N];
bool ok[N],graph[N][N];
int find(int x,int C){
	if (vis[x]==C) return 0;
	for (int i=head[x];i;i=next[i])
	if (vis[w[i]]!=C&&ok[w[i]]){
		vis[w[i]]=C;
		if (!match[w[i]]||find(match[w[i]],C)){
			match[w[i]]=x;
			return 1;
		}
	}
	return 0;
}
void solve(){
	for (int i=1;i<=B;i++){
		match[i]=0;
		if (ok[i]) flow++;
	}
	static int C=0;
	for (int i=1;i<=B;i++)
		if (!match[i]&&ok[i]&&(b[i]&1))
			flow-=find(i,++C);
}
int main()
{
	freopen("friends.in","r",stdin);
	freopen("friends.out","w",stdout);
	int T;scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&A,&B,&M);
		for (int i=1;i<=A;i++) scanf("%d",&a[i]);
		for (int i=1;i<=B;i++) scanf("%d",&b[i]);
		while (cnt) next[cnt--]=0;
		for (int i=1;i<=B;i++) head[i]=0;
		for (int i=1;i<=B;i++)
		if (b[i]&1){
			for (int j=1;j<=B;j++)
			if (!(b[j]&1)&&!check(b[i]|b[j]))
				add(i,j);
		}
		for (int i=1;i<=A;i++)
		for (int j=1;j<=B;j++)
			graph[i][j]=0;
		while (M--){
			int x,y;
			scanf("%d%d",&x,&y);
			graph[x][y]=1;
		}
		int ans=0;
		for (int i=1;i<=A;i++)
		for (int j=i+1;j<=A;j++)
		if ((a[i]^a[j])&1){
			for (int k=1;k<=B;k++)
				ok[k]=graph[i][k]&&graph[j][k];
			flow=2;
			solve();
			ans=max(ans,flow);
		}
		for (int i=1;i<=A;i++){
			for (int k=1;k<=B;k++) ok[k]=graph[i][k];
			flow=1;
			solve();
			ans=max(ans,flow);
		}
		for (int k=1;k<=B;k++) ok[k]=1;
		flow=0;
		solve();
		ans=max(ans,flow);
		printf("%d\n",ans);
	}
	return 0;
}