You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Berland 的公路网络由 $n$ 个城市和 $m$ 条双向公路组成。城市编号为 $1$ 到 $n$，其中主首都编号为 $n$，文化首都编号为 $1$。该公路网络保证任意两个城市都可以通过公路互达。每条公路，无论行驶方向如何，所需时间都相同。

Berland 的居民都非常懒惰，因此当他们想从城市 $v$ 到城市 $u$ 时，总会选择一条最短路径（无所谓是哪一条）。

为了让国家的公路网络更安全，政府准备在某一个城市设立一个警察局。警察局有一个奇特的属性：若公路的一端是有警察局的城市，居民在经过这条路时会更加小心，因此这条路被视为安全的。如果一条路的两个端点都不是设有警察局的城市，则这条路是危险的。

现在，政府希望知道将警察局设在某个城市后，使得从文化首都到主首都的所有最短路径上的安全道路的平均数量最大，这个最大值是多少。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2\le n\le 100$，$1\le m\le\frac{n(n-1)}{2}$）——表示 Berland 拥有的城市数和公路数。接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1\le v_i,u_i\le n$，$v_i\ne u_i$），表示第 $i$ 条公路连接了编号为 $v_i$ 和 $u_i$ 的两个城市。每行的数字之间用空格隔开。

保证任意两个城市之间最多只有一条公路，并且整个公路网络是连通的。

输出格式

输出将警察局设在某一城市后，从文化首都到主首都所有最短路径上的安全公路数量的平均数的最大可能值。你的答案只要绝对误差或者相对误差不超过 $10^{-6}$ 即可。

4 4
1 2
2 4
1 3
3 4

1.000000000000

11 14
1 2
1 3
2 4
3 4
4 5
4 6
5 11
6 11
1 8
8 9
9 7
11 7
1 10
10 4

1.714285714286

说明/提示

在第一个样例中，可以将警察局设置在任一首都城市，那么每条路径上都会有且只有一条安全道路。如果放在其他城市，平均安全道路数同样也只有 $1$。

在第二个样例中，将警察局放在城市 $4$ 时，可以使 $6$ 条路径各有 $2$ 条安全道路，另外 $1$ 条路径有 $0$ 条安全道路，因此答案为 $\frac{6 \times 2 + 1 \times 0}{7} = \frac{12}{7}$。