807. [USACO Hol10] 臭气弹

【题目描述】

奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含 $1$ 到 $N$ 共 $N$ 个猪城 $(2 \leq N \leq 300)$。这些城市由 $M (1 \leq M \leq 44850)$ 条由两个不同端点 $A_j$ 和 $B_j (1 \leq A_j \leq N; 1 \leq B_j \leq N)$表示的双向道路连接。保证城市 $1$ 至少连接一个其它的城市。

一开始臭气弹会被放在城市 $1$。每个小时（包括第一个小时），它有 $P/Q (1 \leq P \leq 1,000,000; 1 \leq Q \leq 1,000,000)$ 的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市，那麽它随机地选择一条道路，在这个小时内沿着这条道路走到一个新的城市。

可以离开这个城市的所有道路被选择的概率均等。

因为这个臭气弹的随机的性质，奶牛们很困惑哪个城市最有可能被污染。给定一个猪猡文明的地图和臭气弹在每个小时内爆炸的概率。计算每个城市最终被污染的概率。

如下例，假设这个猪猡文明有两个连接在一起的城市。臭气炸弹从城市 $1$ 出发，每到一个城市，它都有 $1/2$ 的概率爆炸。

                           $1$--$2$

可知下面这些路径是炸弹可能经过的路径（最后一个城市是臭气弹爆炸的城市）：

1: 1

2: 1-2

3: 1-2-1

4: 1-2-1-2

5: 1-2-1-2-1

...

要得到炸弹在城市 $1$ 终止的概率，我们可以把上面的第 $1$，第 $3$，第 $5$ ……条路径的概率加起来，（也就是上表奇数编号的路径）。上表中第 $k$ 条路径的概率正好是 $(1/2)^k$，也就是必须在前 $k-1$ 个回合离开所在城市（每次的概率为 $1 - 1/2 = 1/2）$ 并且留在最后一个城市（概率为 $1/2$）。

所以在城市 $1$ 结束的概率可以表示为 $1/2 + (1/2)^3 + (1/2)^5 + ...$。当我们无限地计算把这些项一个个加起来，我们最后会恰好得到 $2/3$，也就是我们要求的概率，大约是 $0.666666667$。这意味着最终停留在城市 $2$ 的概率为 $1/3$，大约为 $0.333333333$。

你将会在你前 $50$ 次提交的时候得到部份测试数据反馈。

【输入格式】

$*$ 第 $1$ 行: 四个由空格隔开的整数: $N, M, P$, 和 $Q$

$*$ 第 $2$ 到第 $M+1$ 行: 第 $i+1$ 行用两个由空格隔开的整数 $A_j$ 和 $B_j$ 表示一条道路。

【输出格式】

$*$ 第 $1$ 到第 $N$ 行: 在第 $i$ 行，用一个浮点数输出城市 $i$ 被摧毁的概率。

误差不超过 $10^{-6}$ 的答案会被接受（就是说你需要至少输出 $6$ 位有效数字使得答案有效）。

【样例输入】

2 1 1 2
1 2

【样例输出】

0.666666667
0.333333333