Description

Xiao C and Xiao G often study game theory together. One day they came up with the following game—

There is an undirected graph with $n$ vertices and $m$ edges. Initially, each vertex has a color: either black or white.

For each edge, they make one decision: either flip the colors of both endpoints of this edge (black becomes white, white becomes black), or do nothing.

They want to make all vertices white, so they would like to know, among all $2^m$ possible decisions, how many ways can achieve this goal.

However, Xiao G thinks this is too easy, so he also wants to know, for the $i$-th vertex, after deleting this vertex and all edges incident to it, what the new answer is.

Since the answer can be large, you only need to output the result modulo $10^9+7$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains two integers $n, m$, the numbers of vertices and edges.

The next $m$ lines each contain two integers $u, v$, describing an undirected edge $(u, v)$.

Then one line contains a binary string of length $n$:

• If the $i$-th character is $\tt 0$, vertex $i$ is white.
• If the $i$-th character is $\tt 1$, vertex $i$ is black.

Output Format

For each test case, output one line with $n+1$ integers: The first integer is the answer when no vertex is deleted (do not add a line break right after printing it); then output $n$ integers, where the $i$-th is the answer after deleting vertex $i$. Each answer is taken modulo $10^9+7$.

2
5 5
1 2
2 3
3 4
2 4
3 5
00000
5 4
1 2
2 3
2 4
2 5
11111

2 2 1 1 1 2
0 1 0 1 1 1

Hint

Constraints: For all testdata, $1 \le T \le 10^5, 1 \le n, m \le 10^5, 1 \le u, v \le n$, and the given undirected graph has no multiple edges or self-loops.

[Source: HAOI2018 Day 1 T2]

Translated by ChatGPT 5