Driving Out the Piggies

The Cows have built a randomized stink bomb to drive the Piggies out of their land. The Piggy civilization has $N$ cities, numbered $1$ through $N$, connected by $M$ bidirectional roads. Each road joins two different cities, and city $1$ is guaranteed to be connected to at least one other city.

The stink bomb is placed in city $1$. Every hour — including the very first one — the bomb sits in some city and does exactly one of two things:

• With probability $\frac{P}{Q}$ it detonates, polluting the city it currently occupies, and the process stops.
• Otherwise (with probability $1 - \frac{P}{Q}$) it does not detonate. It then chooses one of the roads leaving its current city uniformly at random and travels along it to the neighboring city. Every road leaving a city is equally likely to be chosen.

Because the bomb wanders at random, the Cows want to know, for every city, the probability that the bomb eventually detonates there (polluting it).

For example, suppose there are two cities joined by a single road, and the bomb — starting in city $1$ — detonates with probability $\frac{1}{2}$ each time it enters a city:

1--2

Writing each possible journey as the sequence of cities the bomb visits (it detonates in the last city listed), the journeys are:

1
1-2
1-2-1
1-2-1-2
1-2-1-2-1
...

The bomb detonates in city $1$ exactly on the journeys that pass through an odd number of cities (1; 1-2-1; 1-2-1-2-1; and so on). A journey through $k$ cities occurs with probability $\left(\frac{1}{2}\right)^k$: the bomb must fail to detonate in each of the first $k-1$ cities (probability $1-\frac{1}{2}=\frac{1}{2}$ each) and then detonate in the $k$-th (probability $\frac{1}{2}$). Summing the odd-numbered terms gives the probability of detonating in city $1$:

$$\frac{1}{2} + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^5 + \cdots = \frac{2}{3} \approx 0.666666667$$

so the probability of detonating in city $2$ is $\frac{1}{3} \approx 0.333333333$.

• Line 1: four space-separated integers $N$, $M$, $P$, and $Q$ ($2 \le N \le 300$; $1 \le M \le 44850$; $1 \le P \le 10^6$; $1 \le Q \le 10^6$; $P \le Q$).
• Lines 2 to $M+1$: each line contains two space-separated integers $A_j$ and $B_j$ ($1 \le A_j \le N$; $1 \le B_j \le N$; $A_j \ne B_j$), describing a bidirectional road between cities $A_j$ and $B_j$.

Print $N$ lines. On line $i$, print the probability that city $i$ is polluted, written with exactly $9$ digits after the decimal point.