记录编号	277125	评测结果	AAAAAAAAAA
题目名称	[SPOJ 839] 最优标号	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2016-07-04 20:16:58	内存使用	0.93 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=1000000000;
const int maxn=1010;
const int maxm=30010;
int cnt,fir[maxn],to[maxm],nxt[maxm],cap[maxm];
void addedge(int a,int b,int c){
	nxt[++cnt]=fir[a];
	fir[a]=cnt;
	cap[cnt]=c;
	to[cnt]=b;
}

queue<int>q;
int dis[maxn];
bool BFS(int s,int t){
	dis[t]=1;q.push(t);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=nxt[i])
			if(!dis[to[i]]){
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
	}	
	return dis[s];
}

int fron[maxn];
int gap[maxn],path[maxn];
int ISAP(int s,int t){
	if(!BFS(s,t))return 0;
	for(int i=s;i<=t;i++)++gap[dis[i]];
	for(int i=s;i<=t;i++)fron[i]=fir[i];
	int p=s,ret=0,f;
	while(dis[s]<=t+1){
		if(p==t){
			f=INF;
			while(p!=s){
				f=min(f,cap[path[p]]);
				p=to[path[p]^1];				
			}
			ret+=f;p=t;
			while(p!=s){
				cap[path[p]]-=f;
				cap[path[p]^1]+=f;
				p=to[path[p]^1];
			}
		}
		int &ii=fron[p];
		for(;ii;ii=nxt[ii])
			if(cap[ii]&&dis[p]==dis[to[ii]]+1)
				break;
		if(ii)
			path[p=to[ii]]=ii;
		else{
			if(--gap[dis[p]]==0)break;
			int minn=t+1;
			for(int i=fir[p];i;i=nxt[i])
				if(cap[i])minn=min(minn,dis[to[i]]);
			++gap[dis[p]=minn+1];ii=fir[p];
			if(p!=s)p=to[path[p]^1];	
		}			
	}
	return ret;
}

void Init(){
	memset(fir,0,sizeof(fir));
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	cnt=1;
}

int n,m,T;
long long ans[maxn],w[maxn];
int E[maxm][2],fa[maxn],fa2[maxn];
int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}
int Find2(int x){
	return fa2[x]==x?x:fa2[x]=Find2(fa2[x]);
}
long long Solve(){
	int s=0,t=n+1;
	long long ret=0;
	for(int k=0;k<=30;k++){
		Init();
		fa2[s]=s;fa2[t]=t;
		for(int i=1;i<=n;i++)fa2[i]=i;
		for(int i=1;i<=n;i++)
			if(Find(i)==0&&w[i]!=-1){
				if(w[i]>>k&1){
					addedge(s,i,INF);
					addedge(i,s,0);
				}
				else{
					addedge(i,t,INF);
					addedge(t,i,0);
				}
			}
		for(int i=1;i<=m;i++)
			if(Find(E[i][0])==0){
				addedge(E[i][0],E[i][1],1);
				addedge(E[i][1],E[i][0],1);
			}
		ret+=(1ll<<k)*ISAP(s,t);
		for(int i=2,u,v;i<=cnt;i++)
			if(cap[i]){
				v=Find2(to[i]);
				u=Find2(to[i^1]);
				if(u>v)swap(u,v);
				if(u!=v)fa2[v]=u;
			}
		for(int i=1;i<=n;i++){
			if(w[i]==-1&&!Find2(i))
				ans[i]|=1<<k;
		}
	}
	return ret;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
#endif
T=1;	
	//scanf("%d",&T);
	while(T--){	
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			for(int j=0;j<=1;j++)
				scanf("%d",&E[i][j]);
		
		int u,v,k;
		scanf("%d",&k);
		memset(w,-1,sizeof(w));
		memset(ans,0,sizeof(ans));
		while(k--){
			scanf("%d",&u);
			scanf("%lld",&w[u]);
		}
		
		for(int i=1;i<=n;i++)
			fa[i]=w[i]!=-1?0:i;
		
		for(int i=1;i<=m;i++){
			u=Find(E[i][0]);
			v=Find(E[i][1]);
			if(u>v)swap(u,v);
			if(u!=v)fa[v]=u;
		}
		printf("%lld\n",Solve());
		/*
		for(int i=1;i<=n;i++)
			if(w[i]==-1)
				printf("%lld\n",ans[i]);
			else 
				printf("%lld\n",w[i]);	
		*/
	}
	return 0;
}