小H学地理
题号：NC281540
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

小H今天在学校里学习了地理，小H了解到我国地大物博，幅员辽阔，于是小H想去游玩一番祖国的大好河山。小H提前制定好了旅游线路计划，包括 个旅游景点，景点编号由 1 到 ， 条连接不同景点的路线，其中每个景点都可以通过路线走到。但是小H哪个都想游玩，也不想安排游玩顺序，于是小H决定从景点 1 出发，以相同概率前往相邻的景点，直到游玩到景点 ，结束旅行。每个景点最终的游玩乐趣 与最终游玩次数 有关，且由景点游玩新鲜度 和审美疲劳度 决定，具体表达式为 。
小H想知道所有景点最终的游玩乐趣的期望值之和是多少，小H提前列好了景点有趣程度和审美疲劳度的个性化列表，但是粗心的小H忘记了标记景点编号，列表上只有 条成对信息。因此最终的所有景点最终的游玩乐趣的期望值有多种可能，小H非常乐观，因此他想知道所有可能的期望值之中最大的是多少？
题目保证图是连通的且无重边和自环。

输入描述:

第一行输入两个正整数 n, m，表示有 n 个景点，m 条路线。
接下来 n 行，每行输入两个正整数 a, b，表示景点的审美疲劳度和游玩新鲜度。
接下来 m 行，每行输入两个正整数 u, v，表示景点 u, v 之间有一条线路。
1\leq n \leq300
0\leq m\leq \frac{n(n-1)}{2}
1\leq a,b \leq10^5

输出描述:

一个浮点数，表示最大可能的期望值，如果答案的绝对误差或相对误差不超过 10^{-6} ，则认为答案正确。
形式上，假设你的答案为 x，标准答案为 y。当且仅当 \frac{|x-y|}{max(1,|y|)} \leq10^{-6} 时，你的答案被认为是正确的。
示例1

输入

复制 
3 2
2 7
1 3
3 7
1 2
2 3

输出

复制 
6.0000000000

说明

最终游玩次数期望依次为\lbrace 2,2,1\rbrace,游玩次数平方期望依次为\lbrace 6,6,1\rbrace,
此时个性化列表依次为 \lbrace (2,7),(1,3),(3,7)\rbrace,总期望值最大
示例2

输入

复制 
3 3
3 2
5 7
1 1
1 2
1 3
2 3

输出

复制 
-0.8888888889

说明

最终游玩次数期望依次为\lbrace \frac{4}{3},\frac{2}{3},1\rbrace,游玩次数平方期望依次为\lbrace \frac{20}{9},\frac{10}{9},1\rbrace,
此时个性化列表依次为 \lbrace (1,1),(3,2),(5,7)\rbrace,总期望值最大

备注: