[HAOI2018]反色游戏

题目描述

小$C$和小$G$经常在一起研究搏弈论问题,有一天他们想到了这样一个游戏. 有一个$n$个点$m$条边的无向图,初始时每个节点有一个颜色,要么是黑色,要 么是白色.现在他们对于每条边做出一次抉择:要么将这条边连接的两个节点都 反色(黑变白,白变黑),要么不作处理.他们想把所有节点都变为白色,他们 想知道在$2^m$种决策中,有多少种方案能达成这个目标. 小$G$认为这个问题太水了,于是他还想知道,对于第$i$个点,在删去这个点及 与它相连的边后,新的答案是多少. 由于答案可能很大,你只需要输出答案对$10^9+7$取模后的结果.

输入输出格式

输入格式


从文件$game.in$中读入数据. 第一行一个整数$T$,表示数据组数. 每组数据第一行两个整数$n$,$m$表示点数和边数. 接下来$m$行,每行两个整数$u$,$v$,描述无向图的一条边. 接下来一行一个长度为$n$的$0/1$串,如果第$i$个字符为$0$表示第$i$个点为白色,否 则为黑色.

输出格式


输出到文件$game.out$中. 每组数据输出一行$n+1$个整数,第一个整数表示不删去任何点时的答案.接 下来$n$个整数,第$i$个表示删去第$i$个点时的答案.

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

对于所有数据,有$1\le T\le5$,$1\le n,m\le10^5$,$1\le u,v\le n$,没有重边和自 环. ![](https://cdn.luogu.com.cn/upload/pic/18145.png) HAOI2018 round1 T2