题意

给出一个有 $n$ 个节点和 $m$ 条边的无向图 $G$，每个点又被涂成黑色或者白色。

现在你有一种操作：

• 翻转一条边两端的点的颜色。

一共有两问：

1. 按照上面的操作，将整张图变为白色的方案数。
2. 对于每一个点 $u$，如果将其删除，则有多少种方案能将整张图变为白色。

分析

第一问

我们选择一条边，如果起点和终点都是同一种颜色 $C$，那么 $cnt_{C_1} \leftarrow cnt_{C_1} - 2$。

如果这条边的两端点的颜色分别是 $C_0$ 和 $C_1$，那么反转这条边，就会使得 $cnt_{C_0} - 1 + 1 = cnt_{C_0}$，$cnt_{C_1} - 1 + 1 = cnt_{C_1}$。

观察上面的式子就会发现，我们的每次操作都不会影响每个点数量的奇偶性。众所周知，$0$ 的奇偶性是偶。于是我们就得到了如下结论：

:::align{center} 当且仅当黑点的个数为偶数时，方案数不为 $0$。 :::

那么对于有偶数个黑点的一棵树，其全部变为白色必然只有一种方案。

::::success[证明] 对于每次操作，我们都钦定目的是将这条边的儿子变为白色。

于是就有下面两种情况：

1. 若子节点为白色，则不反转这条边。
2. 若子节点为黑色，则反转这条边。

对于有偶数个黑点的树，对于树上的每一条边，都有且仅有一种决策方案。

有且仅有一种方案使得树上全部为白点。 ::::

假设整张图有 $1$ 个连通块，那么这个连通块就可以有 $m - n + 1$ 个树边的选择方案，那么答案就是 $2^{m - n + 1}$ 种方案。

推广一下，就可以得到第一问的答案 $2^{m - n + k}$ 了。其中 $k$ 表示图中有 $k$ 个连通块。

第二问

现在需要考虑删点了。

对于原始的图，我们建一棵圆方树。

::::info[圆方树] 圆方树就是一颗有圆点和方点的树。

其中的圆点表示原来图上的点。

方点比较特殊，它是一种新建立的点，表示一个点双连通分量。

建完圆、方点之后，我们把每一个点双连通分量都与它们的方点相连。

题外话：这个时候就会发现每个点双都变成了一个菊花图，会具有一些优秀的性质。虽然跟这道题没什么关系。 ::::

接下来，我们的讨论都会在这棵圆方树上进行。

对于要删除的点 $u$，我们令与其相连的方点数量为 $d_u$。容易发现删除这个点之后新增的连通块的数量就是 $d_u - 1$。

知道了连通块的数量，那么根据刚才的公式，答案的计算就非常简单了。

直接在圆方树上跑一遍 DFS。

• 记录每一个点是否是割点（只需要判断这个点在圆方树上的度数即可）。
• 在跑 DFS 的时候去记录每个点的所有子节点所在的子树中有多少个黑点。

最后对于每个询问的点 $u$，直接判断有无解，有解则输出 $2^{(m - de_u) - (n - 1) + (k + d_u - 1)}$，其中 $de_u$ 表示在原图中点 $u$ 的度数。

需要注意的是，原图可能有多个有奇数个黑点的连通块，这个时候只需要特判一下即可。

::::success[code]

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;

inline int qpow(int x, int k){
	int res = 1;
	while(k){
		if(k & 1) res = res * x % mod;
		x = x * x % mod, k >>= 1;
	}
	return res;
}

int t;
int n, m;
string s;

vector<int> e[N];
int k, k2, cnt, sum, de[N];
inline void add(int u, int v){
	e[u].push_back(v), e[v].push_back(u);
	++ de[u], ++ de[v];
}

vector<int> rst[N];
int d[N], is[N], is2[N], siz[N];
bool vis[N];

int dfn[N], low[N], tim;
int stk[N], stk2[N], top, top2;

inline void init(){
    for(int i = 0; i < N; i++){
        e[i].clear();
        rst[i].clear();
    }
	memset(de, 0, sizeof(de));
	memset(d, 0, sizeof(d));
	memset(is, 0, sizeof(is));
	memset(is2, 0, sizeof(is2));
	memset(vis, 0, sizeof(vis));
	memset(siz, 0, sizeof(siz));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	
	k = k2 = sum = tim = top = top2 = 0;
    cnt = n;
}

void tarjan(int u){
	dfn[u] = low[u] = ++ tim;
	if(s[u] == '1') ++ sum;
	
	stk[++ top] = u;
	stk2[++ top2] = u;
	
	for(auto v : e[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
			
			if(low[v] == dfn[u]){
				++ cnt;
                int y;
                do{
                    y = stk[top --];
                    ++ d[y];
                    rst[cnt].push_back(y);
                    rst[y].push_back(cnt);
                } while(y != v);
                rst[cnt].push_back(u);
                rst[u].push_back(cnt);
                d[u]++;
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}

void dfs(int u){
    stk[++top] = u, vis[u] = 1, siz[u] = (u <= n && s[u] == '1');
	
	for(auto v : rst[u]){
		if(vis[v]) continue;
		dfs(v); 
		siz[u] += siz[v];
		if(u <= n && (siz[v] & 1)) is[u] = 1;
	}
}

inline void solve(){
	cin >> n >> m;
	init();
	
	for(int i = 1; i <= m; ++ i){ 
        int u, v; 
        cin >> u >> v; 
        add(u, v); 
    }
	cin >> s; 
    s = ' ' + s;
	
	bool flag = true;
	for(int i = 1; i <= n; ++ i){
		if(!dfn[i]){
			sum = 0; 
            top2 = 0;
			++ k;
			tarjan(i);
			
			if(sum & 1){
				++ k2;
				flag = false;
				for(int j = 1; j <= top2; ++ j) 
                    is2[stk2[j]] = 1;
			}
		}
	}
	
	if(flag) cout << qpow(2, m - n + k) << ' ';
	else cout << "0 ";
	
	if(k2 > 1){
		for(int i = 1; i <= n; ++ i) cout << "0 ";
		cout << '\n';
		return ;
	}
	
	memset(vis, 0, sizeof(vis));
	memset(is, 0, sizeof(is));
	
	for(int i = 1; i <= n; ++ i){
		if(!vis[i]){
			top = 0; dfs(i);
			
			for(int j = 1; j <= top; ++ j){
				int node = stk[j];
				if(node <= n && ((siz[i] - siz[node]) & 1)) 
					is[node] = 1;
			}
		}
	}
	
	for(int i = 1; i <= n; ++ i){
		if(is[i] || (!flag && !is2[i])) cout << "0 ";
		else cout << qpow(2, (m - de[i]) - (n - 1) + (k + d[i] - 1)) << ' ';
	}
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
	cin >> t;
	while(t --) solve();
	
	return 0;
}

::::