题意：略
怎样判断属于S,T集合。
如果从S出发到不了某点，该点出发也到不了T，那么割给那边都行。
如果S出发能到该点，该点出发也能到T，这种情况下dinic没结束。
只能从S到该点：只能分到S集。只能从该点到T，T集。
这题中两种都能分到时，假如S表示0，那贪心分到S。这样只要看它能不能到T，如果能到T,一定要选1，否则就选0.用类似SPFA的操作。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
using namespace std;
const double EPS=1e-;
typedef long long lon;
const lon SZ=,SSZ=,APB=,one=,INF=0x7FFFFFFF,mod=;
int n,m,src[SZ][SZ],knum,arr[SZ],S=,T=;
int ans[SZ],mp[SZ][SZ],dep[SZ];
bool vst[SZ]; void init()
{
cin>>n>>m;
for(int i=;i<=m;++i)
{
int a,b;
cin>>a>>b;
src[a][b]=src[b][a]=;
}
cin>>knum;
for(int i=;i<=knum;++i)
{
int a,b;
cin>>a>>b;
ans[a]=arr[a]=b;
vst[a]=;
}
} void add(int u,int v,int w)
{
mp[u][v]=w;
} bool bfs()
{
memset(dep,,sizeof(dep));
dep[S]=;
queue<int> q;
q.push(S);
for(;q.size();)
{
int fr=q.front();
q.pop();
for(int i=;i<=T;++i)
{
if(!dep[i]&&mp[fr][i])
{
dep[i]=dep[fr]+;
q.push(i);
if(i==T)return ;
}
}
}
return ;
} int dinic(int x,int flow)
{
if(x==T)return flow;
else
{
int rem=flow;
for(int i=;i<=T&&rem;++i)
{
if(dep[i]==dep[x]+&&mp[x][i])
{
int tmp=dinic(i,min(rem,mp[x][i]));
if(!tmp)dep[i]=;
rem-=tmp;
mp[x][i]-=tmp,mp[i][x]+=tmp;
}
}
return flow-rem;
}
} void build(int x)
{
memcpy(mp,src,sizeof(src));
for(int i=;i<=n;++i)
{
if(vst[i])
{
if(arr[i]&(<<x))
{
add(i,T,INF);
add(T,i,);
}
else
{
add(S,i,INF);
add(i,S,);
}
}
else
{
// add(S,i,APB);
// add(i,S,0);
// add(i,T,APB);
// add(T,i,0);
}
}
} int v2[SZ]; void calc(int x)
{
memset(v2,,sizeof(v2));
queue<int> q;
for(int i=;i<=n;++i)
{
if(mp[i][T])v2[i]=,q.push(i);
}
for(;q.size();)
{
int fr=q.front();
q.pop();
for(int i=;i<=n;++i)
{
if(!v2[i]&&mp[i][fr])
{
v2[i]=;
q.push(i);
}
}
}
for(int i=;i<=n;++i)
{
//if(x==0)cout<<v2[i]<<endl;
if(v2[i]&&!vst[i])ans[i]|=<<x;
}
} void work()
{
for(int i=;i<;++i)
{
build(i);
int res=;
for(;bfs();)res+=dinic(S,INF);
//cout<<"res: "<<res<<endl;
calc(i);
}
for(int i=;i<=n;++i)
{
cout<<ans[i]<<endl;
}
} void release()
{
memset(vst,,sizeof(vst));
memset(src,,sizeof(src));
memset(ans,,sizeof(ans));
} int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
//cout<<(1<<31)<<endl;
int casenum;
cin>>casenum;
//cout<<casenum<<endl;
for(int time=;time<=casenum;++time)
//for(int time=1;scanf(" %s",ch+1)!=EOF;++time)
{
init();
work();
release();
}
return ;
}