part1：建图
二进制异或，每一位互不干扰。所以对每一位分开来考虑。
然后变成了一个经典的模型。
当前每一个未确定点有两个选择：变成 \(1\)，变成 \(0\)；已经确定的点只能选它本身的值。
于是构造思路非常套路了：构造虚点 \(S\)、\(T\)。对于一个点 \(u\)，从 \(S\) 连向 \(u\) 一条边，值为 \(u\) 不取 \(1\) 的代价。从 \(u\) 连向 \(T\) 一条边，表示 \(u\) 不取 \(0\) 的代价。对于原图上的一条边 \((u,v)\)，在网络流的图上 \(u,v\) 间连一条值为 \(1\) 的边。图的最小割就是当前这个二进制位会异或出多少个 \(1\)。
上图是一个例子。\(A\) 点已给出，在当前位上为 \(1\)，\(B\) 点已给出，在当前位上为 \(0\)。\(A,C\) 在原图上有一条边。
\(A\) 不能不取 \(1\)，代价为 \(inf\)，\(B\) 不能不取 \(0\)，代价为 \(inf\)。\(C\) 没有限制，所以两边的代价都是 \(0\).
part2：优化
图中为 \(0\) 的边显然对跑网络流没有影响，可以全部删掉。这个时候，如果一个点 \(u\) 没有初始被赋值，也没有与任何点连边。它就没有与任何边了呀？我怎么知道它取什么值呢？其实这种点你全部给它赋值为 \(0\) 就可以了。
part3：求方案数与一些解释
复习一下最大流怎么对应上最小割？在最终的残留网络上，从 \(S\) 开始 bfs，只走那些不为 \(0\) 的边，能走到的点都划分为 \(S\) 部。
所以在这道题中，在残留网络上从 \(S\) 开始 bfs能走到的点都被我们赋值为 \(1\)，其它点都赋值为 \(0\) 就可以了。
但是还有一个问题，题目中要求 在边权和最小的条件下，点权和最小的方案，上面的做法好像没有保证点权和最小呀？其实在 part2 中，把所有“孤立点”赋值为 \(0\) 已经保证了点权和最小。在优化后的网络流图上，找到一种最小割方案后，你是没有办法调整割的边使点权和更小的。你可以自己画画图稍微思考一下。
part4：代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=505,MAXM=1e5+5;
struct E{int nxt,to,w;}e[MAXM];
int cnt=1;
int head[MAXN],cur[MAXN];
void add(int u,int v,int w){
// printf("%d %d %d\n",u,v,w);
e[++cnt]={head[u],v,w};head[u]=cnt;
e[++cnt]={head[v],u,0};head[v]=cnt;
}
int dis[MAXN];
const int INF=0x3f3f3f3f;
int n,S,T;
bool bfs(){
for(int i=1;i<=n;i++) dis[i]=INF;
dis[S]=0;
queue<int> q;q.push(S);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].w&&dis[v]==INF){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[T]<INF;
}
int dfs(int u,int limit){
if(u==T) return limit;
int ret=0;
for(int i=cur[u];i;i=e[i].nxt){
int v=e[i].to;
cur[u]=i;
if(e[i].w&&dis[v]==dis[u]+1){
int add=dfs(v,min(limit-ret,e[i].w));
if(!add) dis[v]=-1;
ret+=add,e[i].w-=add,e[i^1].w+=add;
if(ret==limit) return ret;
}
}
return ret;
}
int dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=n;i++) cur[i]=head[i];
ans+=dfs(S,INF);
}
return ans;
}
int N,M;
ll a[505],b[505];
int u[3005],v[3005];
bool vis[MAXN];
void find(int u,ll dlt){
vis[u]=1;
if(u!=S) b[u]+=dlt;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].w&&!vis[v]) find(v,dlt);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int wwh;scanf("%d",&wwh);
while(wwh--){
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++) scanf("%d%d",&u[i],&v[i]);
for(int i=1;i<=N;i++) a[i]=-1,b[i]=0;
int K;scanf("%d",&K);
for(int i=1;i<=K;i++){
int x;scanf("%d",&x);
scanf("%lld",&a[x]);
}
n=N+2;S=n-1,T=n;
ll ans=0;
for(int i=30;i>=0;i--){
for(int i=1;i<=n;i++) head[i]=0;
cnt=1;
for(int j=1;j<=N;j++){
if(a[j]==-1) continue;
else{
int op=((a[j]>>i)&1);
op==0?add(j,T,INF):add(S,j,INF);
}
}
for(int j=1;j<=M;j++) add(u[j],v[j],1),add(v[j],u[j],1);
int add=dinic();
for(int j=1;j<=n;j++) vis[j]=0;
find(S,(1ll<<i));
ans+=1ll*add*(1ll<<i);
}
for(int i=1;i<=N;i++){
printf("%lld\n",b[i]);
}
}
return 0;
}