platinum_Island_Vacation (USACO January_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: modular arithmetic, graph theory, probabilistic method, linear algebra

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$,
If there are no bridges adjacent to island $i$ that she has not yet crossed,
she ends her vacation.
Otherwise, with probability $p_i\pmod{10^9+7}$, she ends her vacation.
Otherwise, out of all bridges adjacent to island $i$ that she has not yet
crossed, she chooses one uniformly at random and crosses it.
For each island, output the probability that she ends her vacation at that
island, modulo $10^9+7$.
INPUT FORMAT (input arrives from the terminal / stdin):
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.
OUTPUT FORMAT (print output to the terminal / stdout):
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.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
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$.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
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$.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18
SCORING:
Inputs 4-5: $N\le 11$
Inputs 6-7: There are no simple cycles.
Inputs 8-11: No island lies on more than one simple cycle.
Inputs 12-15: No island lies on more than $5$ simple cycles.
Inputs 16-19: No island lies on more than $50$ simple cycles.
Inputs 20-23: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: