题目描述

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

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

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

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

输入格式

第一行有两个整数 $n,m$ ，分别表示 OItown 里的城堡数（这些城堡用 $1,2,3...,n$ 标号）和地铁线路的数量。

接下来 $m$ 行，每行包含两个整数 $x,y$ ，表示这两个城堡之间有一条地铁线路。注意，两个城堡之间最多只有一条地铁线路，且每条地铁线路只被输入文件描述一次。

最后的 $n$ 行，每行有 $n$ 个整数。第 $i$ 行的第 $j$ 个非负整数 $C_{i,j}$ 表示每天早晨有 $C_{i,j}$ 个 OItown 的居民要从 $i$ 城堡去 $j$ 城堡。数据保证 $C_{i,i}=0$ 。

输出格式

共计 $m$ 行，每行一个实数，依次表示第 $i$ 条地铁线路每天早晨的平均客流 $(1\le i\le m)$。

对每组实数，记答案为 $a$ ，而你的输出为 $b$ ，那么当且仅当 $m$ 组实数均满足 $|a-b|\le 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.3 0.7

样例解释

样例说明：从城堡 $1$ 到城堡 $6$ 的使得换乘次数最少的乘车方式共有 $3$ 种 : 1-2-4-6, 1-2-5-6, 1-3-5-6 。所以每个人都有 $\frac{1}{3}$ 的概率选择这其中的每一种。

数据范围

$1\le n\le 300,~1\le m\le \frac{n(n-1)}{2},~0\le C_{i,j}\le 100$ 。