题目描述

著名的城市交通规划师 L.Serenade 为 OItown 的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度，所以这些地铁线路是可以“交叉”的。

OItown 的居民们的生活和工作都在不同的城堡中进行，于是，每个 OItown 的居民都要在每天早晨从家出发，乘地铁去工作，当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式，这些乘车方式所需要的换乘次数一样，那么居民每天都会等概率的随机选择其中一种。

现在 L.Serenade 想请你为他计算出，每天每条地铁线路在早晨的期望客流量。他会告诉你，每个居民的家和工作地址，还有他设计的地铁交通网络的全部信息。

输入格式

第一行两个正整数 $n,m\ (2 \le n \le 300, n-1 \le m \le \dfrac{n(n-1)}{2})$，表示城堡和线路的个数。

下面 $m$ 行，每行两个正整数 $u,v\ (1 \le u,v \le n, u \ne v)$，表示一条双向线路 $u \leftrightarrow v$。

下面一个 $n \times n$ 的矩阵 $\{C_{n,n}\}\ (0 \le C_{i,j} \le 100,C_{i,i}=0)$，其中 $C_{i,j}$ 表示每天早上进行 $i \to j$ 的出行的居民个数。

L.Serenade 保证，交通网络能把城市连为一体，而且任意两个城堡之间的最优乘车方式（即换乘次数最少的）不超过 $2^{63}-1$ 种。

输出格式

$m$ 行，每行一个一位小数，表示该条线路的期望客流量，绝对误差不得大于 $0.1$。

6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

0.7
0.3
0.3
0.3
0.3
0.3
0.7

提示

样例解释：

唯一一位居民会等概率地从以下三条路径中选择一条：

• $1 \to 2 \to 4 \to 6$
• $1 \to 2 \to 5 \to 6$
• $1 \to 3 \to 5 \to 6$