| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Bessie is taking a vacation in a network of $N$ (2ドル\le N\le 10^4$) islands labeled 1ドル\dots N$ connected by $M$ bidirectional bridges, each of which connects two islands ($N-1\le M\le 3/2(N-1)$). It is guaranteed that the bridges form a connected simple graph (in particular, no two bridges connect the same pair of islands, and no bridge connects an island to itself).
It is also guaranteed that no bridge lies on more than one simple cycle. A simple cycle is a cycle that does not contain repeated islands.
Bessie starts at island 1ドル,ドル and travels according to the following procedure. Supposing she is currently at island $i,ドル
For each island, output the probability that she ends her vacation at that island, modulo 10ドル^9+7$.
The first line contains the number of independent test cases $T$ (1ドル\le T\le 10$). Consecutive test cases are separated by an empty line.
The first line of each test contains $N$ and $M,ドル where $N$ is the number of islands and $M$ is the number of bridges. It is guaranteed that the sum of $N$ over all test cases does not exceed 10ドル^4$.
The second line of each test contains $p_1, p_2,\dots, p_N$ (0ドル\le p_i<10^9+7$).
The next $M$ lines of each test describe the bridges. The $i$th line contains integers $u_i$ and $v_i$ (1ドル\le u_i<v_i\le N$), meaning that the $i$th bridge connects islands $u_i$ and $v_i$. It is guaranteed that the bridges satisfy the constraints mentioned above.
For each test case, output the probability of ending at each island from 1ドル$ to $N$ modulo 10ドル^9+7$ on a single line, separated by spaces.
2 3 2 0 10 111111112 1 3 2 3 6 5 500000004 0 0 0 0 0 1 5 1 3 4 5 5 6 1 2
0 888888896 111111112 500000004 166666668 166666668 83333334 0 83333334
For the first test case, $p_3\equiv 1/9 \pmod{10^9+7}$. Bessie has probability 1ドル/9$ of ending at 3ドル$ (taking the path 1ドル\to 3$) and 8ドル/9$ of ending at 2ドル$ (taking the path 1ドル\to 3\to 2$).
For the second test case, $p_1\equiv 1/2\pmod{10^9+7}$. Bessie has probability 1ドル/2$ of ending at 1ドル,ドル 1ドル/6$ of ending at each of 2ドル$ or 3ドル,ドル and 1ドル/12$ of ending at each of 4ドル$ or 6ドル$.
2 5 5 333333336 333333336 0 0 0 1 2 2 3 3 4 4 5 1 5 5 5 0 0 0 0 0 1 2 2 3 2 4 1 4 1 5
777777784 222222224 0 0 0 0 0 333333336 0 666666672
For the first test case, $p_1\equiv p_2\equiv 1/3\pmod{10^9+7}$. Bessie has probability 7ドル/9$ of ending at 1ドル$ (taking one of the paths 1ドル,ドル 1ドル\to 2\to 3\to 4\to 5\to 1,ドル or 1ドル\to 5\to 4\to 3\to 2\to 1$) and 2ドル/9$ of ending at 2ドル$.
For the second test case, Bessie has probability 1ドル/3$ of ending at 3ドル,ドル and 2ドル/3$ of ending at 5ドル$.
1 11 13 2 3 4 5 6 7 8 9 10 11 12 1 2 1 3 2 3 2 4 4 5 2 5 4 8 5 9 2 6 6 7 2 7 6 10 5 11
133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18