Polluted Piggy Cities

The Piggy civilization is represented by a graph with N cities and M bidirectional roads. A randomized stink bomb is deployed at city 1. Every hour (including the first), the bomb has a probability \(\frac{P}{Q}\) of detonating in its current city. If it does not go off, it randomly picks one of the outgoing roads (all roads are equally likely) and moves to the adjacent city. When the bomb detonates, it pollutes the city it occupies.

Your task is to compute, for each city, the probability that it becomes polluted. Formally, let \(d = \frac{P}{Q}\) and let the transition probability from city \(u\) to city \(v\) be \(\frac{1-d}{\deg(u)}\) if there is a road between \(u\) and \(v\) (where \(\deg(u)\) is the degree of city \(u\)). Then the absorption probability at city \(i\) (i.e. the probability that the bomb detonates in \(i\)) when starting from city 1 is given by

[ x_i = d \sum_{k \ge 0} (1-d)^k (T^k){1,i} = d\cdot\Bigl(I-(1-d)T\Bigr)^{-1}{1,i}, \quad 1 \le i \le N. ]

It can be shown that the bomb eventually detonates with probability 1. Use the above idea to set up a system of linear equations: define \(y(i)\) as the expected number of visits to city \(i\) (including the first visit) before the bomb detonates. Then for every city \(v\) (with cities numbered from 1 to \(N\)) we have:

[ y(v) = \begin{cases} 1 + (1-d)\sum_{u:,u\sim v} \frac{y(u)}{\deg(u)} & \text{if } v=1,\[1mm] (1-d)\sum_{u:,u\sim v} \frac{y(u)}{\deg(u)} & \text{if } v\neq 1, \end{cases} ]

Then the probability that city \(i\) is polluted is \(x_i = d\cdot y(i)\).

Print the pollution probability for each city with 9 decimal places of precision.

inputFormat

The first line contains four integers: N M P Q, where N (2 ≤ N ≤ 300) is the number of cities, M (1 ≤ M ≤ 44,850) is the number of bidirectional roads, and \(d=\frac{P}{Q}\) (1 ≤ P ≤ 1,000,000, 1 ≤ Q ≤ 1,000,000, P ≤ Q) is the probability of detonation each hour.

Then M lines follow, each containing two integers A_j and B_j (1 ≤ A_j, B_j ≤ N) indicating a road connecting cities A_j and B_j. City 1 is guaranteed to be connected to at least one other city.

outputFormat

Output N lines. The i-th line should contain the probability that the bomb detonates (and pollutes) city i, printed with 9 decimal places.

sample

2 1 1 2
1 2

0.666666667
0.333333333