伯兰德道路网络由 n 个城市和 m 条双向道路组成。城市编号从1到 n，其中主要首都城市编号为 n，文化首都城市编号为 1。道路网络设置为可以通过道路从任意一个城市到达任意其他城市。沿着每条道路的任何方向行驶所需的时间相同。

伯兰德的所有居民都非常懒，所以当他们想从城市 v 到城市 u 时，他们总是选择其中一条最短的路径（无论是哪一条）。

伯兰德政府希望使这个国家的道路网络更安全。为此，他们打算在一个城市建立一个警察局。警察局有一个相当奇特的特性：当伯兰德的市民沿着有警察局的一端的道路行驶时，市民会更加小心，因此所有这样的道路都被认为是安全的。两端与有警察局的城市不同的道路是危险的。

现在政府想知道在哪个城市建立警察局，使得从文化首都到主要首都的所有最短路径的平均安全道路数量的值最大。

第一行输入包含两个整数 n 和 m (2 ≤ n ≤ 100, ) — 伯兰德中的城市数量和道路数量，依次为。接下来的 m 行包含一对整数 v_i, u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — 第 i 条道路连接的城市编号。一行上的数字用空格分隔。

保证每一对城市之间最多只有一条道路相连，并且可以通过伯兰德的道路从任意一个城市到达任意其他城市。

输出从文化首都到主要首都的所有最短路径中安全道路的平均数量的最大可能值。如果答案的绝对或相对误差不超过 10^- 6，则答案将被视为有效。