C0585 [ZJOI2014]星系调查

银河历 59451 年，在银河系有许许多多已被人类殖民的星系。如果想要在行星系间往来，大家一般使用连接两个行星系的跳跃星门。

一个跳跃星门可以把物质在它所连接的两个行星系中互相传送。

露露、花花和萱萱被银河系星际联盟调查局任命调查商业巨擘 ZeusLeague+ 的不正当商业行为。

在银河系有 $N$ 个已被 ZeusLeague+ 成功打入市场的行星系，不妨标号为 $1,2,\ldots,N$。而 ZeusLeague+ 在这 $N$ 个行星系之间还拥有自己的 $M$ 个跳跃星门。使用这些跳跃星门，ZeusLeague+ 的物资就可以在这 $N$ 个行星系中两两任意互相传输。由于经费问题，跳跃星门的个数不会超过行星系的个数。露露在颇费周折之后得到了 ZeusLeague+ 在这 $N$ 个行星系中的各自的贸易总额 $C_i\ (i=1,2,\ldots,N)$。

萱萱设计了一个经济学特征指标 $D_i$ 来度量这 $N$ 个行星系的经济学特征。于是，我们可以用二元组 $(C_i,D_i)$ 来表示第 $i$ 个行星系的 XP (Xuan's Position)。现在假设我们有 $k$ 个行星系的 XPs，把它们放置在二维平面上，然后我们用一条直线去拟合这些 XPs。定义一条直线与 XPs 的相斥度为这条直线到各个 XP 的 Euclid 距离的平方之和。再令 XPs 的线性假设相斥度为所有直线与 XPs 的相斥度中的最小者。那么，这个值越小，ZeusLeague+ 在这 $k$ 个行星系中的相互贸易活动就越可疑，从而值得进一步调查。

花花负责计算许多行星系对 $(u,v)$ 的非可疑度。一条跳跃星门航线的非可疑度被定义为它经过的所有行星系（包括起点和终点）的 XPs 的线性假设相斥度。而一个行星系对 $(u,v)$ 的非可疑度则被定义为所有以 $u$ 为起点，$v$ 为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始，通过跳跃星门依次到达某些行星系，然后终止，并且中途不重复经过行星系，这样的一个过程。

在花花数天夜以继日的工作之后，平行调查组的你——大名鼎鼎的计算机科学家 Hcceleration.Gerk.Gounce 不忍心看到她这样不眠不休，于是你在完成了手头的工作之后决定帮一帮她。

（无关吐槽：Acceleration 即加速度，jerk 即加速度的导数/位移的三阶导数，jounce 即位移的四阶导数，这名字取得呀…）

样例输入 1

6 6 
3 4 
5 6 
1 3 
4 4 
3 3 
2 4 
1 2 
1 3 
2 3 
2 4 
3 5 
5 6 
3 
3 6 
2 4 
4 6

样例输出 1

0.66667 
0.00000 
1.67544