题目描述
Bessie 正在一个 N(2≤N≤104)座岛组成的岛屿网络中度假,编号为 1…N,由 M 座双向通行的桥连接,每座桥连接两座岛(N−1≤M≤23(N−1))。保证所有桥形成连通的简单图(具体地说,没有两座桥连接同一对岛屿,也没有一座桥连接一座岛到其自身)。
另外保证没有一座桥处在多于一个简单环上。一个简单环是一个不包含重复岛的环。
Bessie 从岛 1 开始,按以下过程旅行。假设她目前在岛 i 上,
- 如果不存在连接岛 i 的她尚未穿过的桥,则她的度假结束。
- 否则,以 pi(mod109+7) 的概率,她的度假结束。
- 否则,在连接岛 i的所有她还没有穿过的桥中,她均匀地随机选择一座并穿过它。
对于每座岛,输出她在该岛上结束度假的概率,对 109+7 取模。
输入格式
输入的第一行包含独立的测试用例的数量 T(1≤T≤10)。相邻的测试用例之间以一个空行分隔。
每一个测试用例的第一行包含 N 和 M,其中 N 为岛的数量,M 为桥的数量。输入保证所有测试用例的 N 之和不超过 104。
第二行包含 p1,p2,…,pN(0≤pi<109+7)。
以下 M 行描述所有的桥。第 i 行包含整数 ui 和 vi(1≤ui<vi≤N),表示第 i 座桥连接岛 ui 和 vi。输入保证所有桥满足上文中的限制。
输出格式
对于每个测试用例输出一行,包含在岛 1 到 N 的每一座岛上结束度假的概率模 109+7 的余数,用空格分隔。
提示
样例解释 1
在第一个测试用例中,p3≡91(mod109+7)。Bessie 有 91 的概率在岛 3 结束(经过路径 1→3),98 的概率在岛 2 结束(经过路径 1→3→2)。
在第二个测试用例中,p1≡21(mod109+7)。Bessie 有 21 的概率在岛 1 结束,各 61 的概率在岛 2 和 3 结束,各 121 的概率在岛 4 和岛 6 结束。
样例解释 2
在第一个测试用例中,p1≡p2≡31(mod109+7)。Bessie 有 97 的概率在岛 1 结束(经过路径 1,1→2→3→4→5→1 与 1→5→4→3→2→1 之一),92 的概率在岛 2 结束。
在第二个测试用例中,Bessie 有 31 的概率在岛 3 结束,32 的概率在岛 5 结束。
测试点性质
- 测试点 4−5:N≤11。
- 测试点 6−7:不存在简单环。
- 测试点 8−11:没有一座岛处在多于一个简单环上。
- 测试点 12−15:没有一座岛处在多于 5 个简单环上。
- 测试点 16−19:没有一座岛处在多于 50 个简单环上。
- 测试点 20−23:没有额外限制。