记录编号	580333	评测结果	AAAAAAAAAA
题目名称	[HAOI 2018]反色游戏	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.671 s
提交时间	2023-07-22 16:18:45	内存使用	5.21 MiB

// Problem: P4494 [HAOI2018] 反色游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4494
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m, sz[maxn], pw[maxn], cnt, cnt_odd, dfn[maxn], low[maxn], deg[maxn], dfc, now, bel[maxn], blo[maxn], cut[maxn];
std::vector<int> G[maxn];
bool tag[maxn];
char s[maxn];

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++ dfc; sz[u] = s[u] == '1'; tag[u] = true; bel[u] = now;
	for(auto& v : G[u]) {
		if(!dfn[v]) {
			tarjan(v, u);
			sz[u] += sz[v];
			if(low[v] >= dfn[u]) {
				blo[u] += sz[v]; ++ cut[u];
				tag[u] &= (sz[v] & 1) == 0;
			}
			low[u] = std::min(low[u], low[v]);
		}
		else if(v != fa)
			low[u] = std::min(low[u], dfn[v]);
	}
	cut[u] -= !fa;
	return ;
}

void work() {
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n;++ i) {
		G[i].clear();
		sz[i] = dfn[i] = low[i] = bel[i] = blo[i] = deg[i] = cut[i] = 0;
	}
	for(int i = 1;i <= m;++ i) {
		int u, v; scanf("%d %d", &u, &v);
		G[u].pb(v), G[v].pb(u), ++ deg[u], ++ deg[v];
	}
	scanf("%s", s + 1);
	cnt = cnt_odd = dfc = 0;
	for(int i = 1;i <= n;++ i)
		if(!dfn[i]) {
			++ cnt;
			tarjan(now = i, 0);
			cnt_odd += sz[i] & 1;
		}
	int ans = m - n + cnt;
	printf("%d ", cnt_odd ? 0 : pw[ans]);
	for(int i = 1;i <= n;++ i) {
		if(!deg[i])
			printf("%d ", cnt_odd - sz[i] ? 0 : pw[ans]);
		else {
			if(tag[i]&&cnt_odd - (sz[bel[i]] & 1) == 0&&((sz[bel[i]] - blo[i] - (s[i] == '1')) & 1) == 0)
				printf("%d ", pw[ans - deg[i] + cut[i] + 1]);
			else
				printf("0 ");
		}
	}
	puts("");
	return ;
}

int main() {
	freopen("2018game.in", "r", stdin);
	freopen("2018game.out", "w", stdout);
	pw[0] = 1;
	for(int i = 1;i <= 100000;++ i)
		pw[i] = 2ll * pw[i - 1] % mod;
	int T; scanf("%d", &T);
	while(T --)
		work();
	return 0;
}