Problem Description

Bessie is on vacation in a network of islands consisting of $N$ ($2 \le N \le 10^4$) islands numbered $1 \ldots N$, connected by $M$ bidirectional bridges, each connecting two islands ($N-1 \le M \le \frac{3(N-1)}{2}$). It is guaranteed that all bridges form a connected simple graph (specifically, no two bridges connect the same pair of islands, and no bridge connects an island to itself).

Additionally, it is guaranteed that no bridge is part of more than one simple cycle. A simple cycle is a cycle that does not contain duplicate islands.

Bessie starts at island $1$ and travels according to the following process. Suppose she is currently on island $i$,

1. If there are no bridges connected to island $i$ that she has not yet crossed, her vacation ends.
2. Otherwise, with probability $p_i \pmod {10^9+7}$, her vacation ends.
3. Otherwise, among all the bridges connected to island $i$ that she has not crossed, she randomly chooses one uniformly and crosses it.

For each island, output the probability that she ends her vacation on that island, modulo $10^9+7$.

Input Format

The first line of input contains the number of independent test cases $T$ ($1 \le T \le 10$). Adjacent test cases are separated by a blank line.

Each test case begins with a line containing $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$ across all test cases does not exceed $10^4$.

The second line contains $p_1, p_2, \ldots, p_N$ ($0 \le p_i < 10^9+7$).

The following $M$ lines describe all the bridges. The $i$-th line contains integers $u_i$ and $v_i$ ($1 \le u_i < v_i \le N$), indicating that the $i$-th bridge connects islands $u_i$ and $v_i$. The input guarantees that all bridges satisfy the constraints mentioned above.

Output Format

For each test case, output one line containing the probabilities that Bessie ends her vacation on islands $1$ to $N$, modulo $10^9+7$, separated by spaces.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

Input Sample #2

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

Output Sample #2

777777784 222222224 0 0 0
0 0 333333336 0 666666672

Input Sample #3

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

Output Sample #3

133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

Notes/Hints

Sample Explanation 1

In the first test case, $p_3 \equiv \frac{1}{9} \pmod {10^9+7}$. Bessie has a $\frac{1}{9}$ probability of ending on island $3$ (via path $1 \to 3$) and an $\frac{8}{9}$ probability of ending on island $2$ (via path $1 \to 3 \to 2$).

In the second test case, $p_1 \equiv \frac{1}{2} \pmod {10^9+7}$. Bessie has a $\frac{1}{2}$ probability of ending on island $1$, a $\frac{1}{6}$ probability of ending on islands $2$ and $3$, and a $\frac{1}{12}$ probability of ending on islands $4$ and $6$.

Sample Explanation 2

In the first test case, $p_1 \equiv p_2 \equiv \frac{1}{3} \pmod {10^9+7}$. Bessie has a $\frac{7}{9}$ probability of ending on island $1$ (via paths $1$, $1 \to 2 \to 3 \to 4 \to 5 \to 1$ and $1 \to 5 \to 4 \to 3 \to 2 \to 1$), and a $\frac{2}{9}$ probability of ending on island $2$.

In the second test case, Bessie has a $\frac{1}{3}$ probability of ending on island $3$ and a $\frac{2}{3}$ probability of ending on island $5$.

Test Case Properties

• Test points $4-5$: $N \le 11$.
• Test points $6-7$: No simple cycles exist.
• Test points $8-11$: No island is part of more than one simple cycle.
• Test points $12-15$: No island is part of more than $5$ simple cycles.
• Test points $16-19$: No island is part of more than $50$ simple cycles.
• Test points $20-23$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分