题目描述

小$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$个点时的答案．

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

提示

对于所有数据，有$1\le T\le5$,$1\le n,m\le10^5$,$1\le u,v\le n$，没有重边和自 环． HAOI2018 round1 T2