SP839

TP

套路满满的题目

直接异或不好算，我们把答案的每一位分开来算，每个点的权值在子问题中只需要填(0)或(1)

异或的性质：同号为(0)，异号为&1&

我们让所有一开始为(1)的点与(S)相连，为(0)的点与(T)相连，流量均为(inf)

图中原本的边连双向边，流量为(1)

那么答案就是最小割啦

最后(S)集合内的点这一位都为(1)

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define y1 qwq 
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
		if(ch=='-') f=0,ch=getchar();
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return f?x:-x;
	}
	const int N=1e5+10,inf=1ll<<60;
	int haku; 
	int n,m,k,st,ed;
	int val[N],ans[N];
	int head[N],cur[N],cnt;
	struct point
	{
		int nxt,to,val;
		point(){}
		point(const int &nxt,const int &to,const int &val):nxt(nxt),to(to),val(val){}
	}a[N<<1];
	inline void link(int x,int y,int z)
	{
		a[++cnt]=(point){head[x],y,z};head[x]=cnt;
		a[++cnt]=(point){head[y],x,0};head[y]=cnt;
	}
	int ex[N],ey[N];
	int dis[N];
	bool vis[N];
	queue<int> q;
	inline bool bfs()
	{
		for(int i=1;i<=ed;++i)
		{
			cur[i]=head[i];
			dis[i]=0;vis[i]=0;
		}
		q.push(st);dis[st]=1;
		while(!q.empty())
		{
			int now=q.front();
			q.pop();
			for(int i=head[now];i;i=a[i].nxt)
			{
				int t=a[i].to;
				if(!dis[t]&&a[i].val)
				{
					dis[t]=dis[now]+1;
					q.push(t);
				}
			}
		}
		return dis[ed];
	}
	inline int dfs(int now,int c)
	{
		if(now==ed||!c) return c;
		int ret=c,f;
		for(int &i=cur[now];i;i=a[i].nxt)
		{
			int t=a[i].to;
			if(dis[t]==dis[now]+1)
			{
				f=dfs(t,min(a[i].val,ret));
				ret-=f;
				a[i].val-=f;
				a[i^1].val+=f;
				if(!ret) return c; 
			}
		}
		if(ret==c) dis[now]=0;
		return c-ret;
	}
	inline void solve(int now)
	{
		vis[now]=1;
		for(int i=head[now];i;i=a[i].nxt)
		{
			int t=a[i].to;
			if(a[i].val&&!vis[t]) solve(t);
		}
	}
	inline void dinic(int k)
	{
		int ret=0;
		while(bfs()) ret+=dfs(st,inf);
		solve(st);
		for(int i=1;i<=n;++i)
		{
			if(vis[i]) ans[i]|=(1<<k);
		}
	}
	inline void main()
	{
		haku=read();
		while(haku--)
		{
			memset(ans,0,sizeof(ans));
			n=read(),m=read();st=n+1,ed=st+1;
			for(int i=1;i<=m;++i) ex[i]=read(),ey[i]=read();
			k=read();
			memset(val,-1,sizeof(val));
			for(int x,y,i=1;i<=k;++i)
			{
				x=read(),y=read();
				val[x]=y;
			}
			for(int k=0;k<31;++k)
			{
				memset(head,0,sizeof(head));cnt=1;
				for(int i=1;i<=n;++i)
				{
					if(val[i]==-1) continue;
					if((val[i]>>k)&1) link(st,i,inf);
					else link(i,ed,inf);
				}
				for(int i=1;i<=m;++i)
				{
					link(ex[i],ey[i],1);
					link(ey[i],ex[i],1);
				}
				dinic(k);
			}
			for(int i=1;i<=n;++i) printf("%lld
",ans[i]);
		}
	}
}
signed main()
{
	red::main();
	return 0;
}