{"problem":{"name":"[USACO24JAN] Island Vacation P","description":{"content":"Bessie 正在一个 $N$（$2\\le N\\le 10^4$）座岛组成的岛屿网络中度假，编号为 $1\\ldots N$，由 $M$ 座双向通行的桥连接，每座桥连接两座岛（$N−1\\le M\\le \\dfrac{3(N-1)}{2}$）。保证所有桥形成连通的简单图（具体地说，没有两座桥连接同一对岛屿，也没有一座桥连接一座岛到其自身）。 另外保证没有一座桥处在多于一个简单环上。一个简单环是一个不","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10140"},"statements":[{"statement_type":"Markdown","content":"Bessie 正在一个 $N$（$2\\le N\\le 10^4$）座岛组成的岛屿网络中度假，编号为 $1\\ldots N$，由 $M$ 座双向通行的桥连接，每座桥连接两座岛（$N−1\\le M\\le \\dfrac{3(N-1)}{2}$）。保证所有桥形成连通的简单图（具体地说，没有两座桥连接同一对岛屿，也没有一座桥连接一座岛到其自身）。\n\n另外保证没有一座桥处在多于一个简单环上。一个简单环是一个不包含重复岛的环。\n\nBessie 从岛 $1$ 开始，按以下过程旅行。假设她目前在岛 $i$ 上，\n\n1. 如果不存在连接岛 $i$ 的她尚未穿过的桥，则她的度假结束。\n2. 否则，以 $p_i \\pmod {10^9+7}$ 的概率，她的度假结束。\n3. 否则，在连接岛 $i$的所有她还没有穿过的桥中，她均匀地随机选择一座并穿过它。\n\n对于每座岛，输出她在该岛上结束度假的概率，对 $10^9+7$ 取模。 \n\n## Input\n\n输入的第一行包含独立的测试用例的数量 $T$（$1\\le T\\le 10$）。相邻的测试用例之间以一个空行分隔。\n\n每一个测试用例的第一行包含 $N$ 和 $M$，其中 $N$ 为岛的数量，$M$ 为桥的数量。输入保证所有测试用例的 $N$ 之和不超过 $10^4$。\n\n第二行包含 $p_1,p_2,\\ldots,p_N$（$0\\le p_i<10^9+7$）。\n\n以下 $M$ 行描述所有的桥。第 $i$ 行包含整数 $u_i$ 和 $v_i$（$1\\le u_i<v_i\\le N$），表示第 $i$ 座桥连接岛 $u_i$ 和 $v_i$。输入保证所有桥满足上文中的限制。 \n\n## Output\n\n对于每个测试用例输出一行，包含在岛 $1$ 到 $N$ 的每一座岛上结束度假的概率模 $10^9+7$ 的余数，用空格分隔。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n在第一个测试用例中，$p_3\\equiv \\frac{1}{9}\\pmod {10^9+7}$。Bessie 有 $\\frac{1}{9}$ 的概率在岛 $3$ 结束（经过路径 $1\\to 3$），$\\frac{8}{9}$ 的概率在岛 $2$ 结束（经过路径 $1\\to 3\\to 2$）。\n\n在第二个测试用例中，$p_1\\equiv \\frac{1}{2}\\pmod {10^9+7}$。Bessie 有 $\\frac{1}{2}$ 的概率在岛 $1$ 结束，各 $\\frac{1}{6}$ 的概率在岛 $2$ 和 $3$ 结束，各 $\\frac{1}{12}$ 的概率在岛 $4$ 和岛 $6$ 结束。\n\n### 样例解释 2\n\n在第一个测试用例中，$p_1\\equiv p_2\\equiv \\frac{1}{3}\\pmod {10^9+7}$。Bessie 有 $\\frac{7}{9}$ 的概率在岛 $1$ 结束（经过路径 $1$，$1\\to 2\\to 3\\to 4\\to 5\\to 1$ 与 $1\\to 5\\to 4\\to 3\\to 2\\to 1$ 之一），$\\frac{2}{9}$ 的概率在岛 $2$ 结束。\n\n在第二个测试用例中，Bessie 有 $\\frac{1}{3}$ 的概率在岛 $3$ 结束，$\\frac{2}{3}$ 的概率在岛 $5$ 结束。\n\n### 测试点性质\n\n- 测试点 $4-5$：$N\\le 11$。\n- 测试点 $6-7$：不存在简单环。\n- 测试点 $8-11$：没有一座岛处在多于一个简单环上。\n- 测试点 $12-15$：没有一座岛处在多于 $5$ 个简单环上。\n- 测试点 $16-19$：没有一座岛处在多于 $50$ 个简单环上。\n- 测试点 $20-23$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10140","tags":["USACO","2024","树形 DP","概率论","圆方树"],"sample_group":[["2\n\n3 2\n0 10 111111112\n1 3\n2 3\n\n6 5\n500000004 0 0 0 0 0\n1 5\n1 3\n4 5\n5 6\n1 2","0 888888896 111111112\n500000004 166666668 166666668 83333334 0 83333334"],["2\n\n5 5\n333333336 333333336 0 0 0\n1 2\n2 3\n3 4\n4 5\n1 5\n\n5 5\n0 0 0 0 0\n1 2\n2 3\n2 4\n1 4\n1 5","777777784 222222224 0 0 0\n0 0 333333336 0 666666672"],["1\n\n11 13\n2 3 4 5 6 7 8 9 10 11 12\n1 2\n1 3\n2 3\n2 4\n4 5\n2 5\n4 8\n5 9\n2 6\n6 7\n2 7\n6 10\n5 11","133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18"]],"created_at":"2026-03-03 11:09:25"}}