CF208C.Police Station

The Berland road network consists of n cities and of m bidirectional roads. The cities are numbered from 1 to n, where the main capital city has number n, and the culture capital — number 1. The road network is set up so that it is possible to reach any city from any other one by the roads. Moving on each road in any direction takes the same time.

All residents of Berland are very lazy people, and so when they want to get from city v to city u, they always choose one of the shortest paths (no matter which one).

The Berland government wants to make this country's road network safer. For that, it is going to put a police station in one city. The police station has a rather strange property: when a citizen of Berland is driving along the road with a police station at one end of it, the citizen drives more carefully, so all such roads are considered safe. The roads, both ends of which differ from the city with the police station, are dangerous.

Now the government wonders where to put the police station so that the average number of safe roads for all the shortest paths from the cultural capital to the main capital would take the maximum value.

伯兰德的道路网络由 $n$ 座城市和 $m$ 条双向道路组成。城市编号为 $1$ 到 $n$，其中主首都城市编号为 $n$，文化首都城市编号为 $1$。该道路网络的结构保证了任意两座城市之间均可通过道路相互到达。沿任一道路在任一方向行驶所需时间均相同。

伯兰德的所有居民都非常懒惰，因此当他们希望从城市 $v$ 前往城市 $u$ 时，总会选择一条最短路径（无论具体是哪一条）。

伯兰德政府希望提升该国道路网络的安全性。为此，政府计划在某一座城市设立一个警察局。该警察局具有一种奇特的性质：当一名伯兰德公民沿某条道路行驶，且该道路的一端恰好是设有警察局的城市时，该公民会更加谨慎地驾驶，因此所有此类道路均被视为安全道路；而两端均不为警察局所在城市的道路则被视为危险道路。

现在，政府希望确定警察局应设在哪座城市，使得从文化首都到主首都的所有最短路径中，安全道路的平均数量达到最大值。

The first input line contains two integers n and m (2 ≤ n ≤ 100, ) — the number of cities and the number of roads in Berland, correspondingly. Next m lines contain pairs of integers v__i, u__i (1 ≤ v__i, u__i ≤ n, v__i ≠ u__i) — the numbers of cities that are connected by the i-th road. The numbers on a line are separated by a space.

It is guaranteed that each pair of cities is connected with no more than one road and that it is possible to get from any city to any other one along Berland roads.

第一行输入包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100$，），分别表示 Berland 的城市数量和道路数量。接下来的 $m$ 行每行包含一对整数 $v_i$、$u_i$（$1 \leq v_i, u_i \leq n$，且 $v_i \neq u_i$），表示第 $i$ 条道路所连接的两座城市的编号。同一行中的数字以空格分隔。

保证任意两座城市之间至多只有一条道路相连，且 Berland 的任意一座城市均可通过道路到达其他任意一座城市。

Print the maximum possible value of the average number of safe roads among all shortest paths from the culture capital to the main one. The answer will be considered valid if its absolute or relative inaccuracy does not exceed 10 - 6.

输出从文化首都到首都的所有最短路径中，安全道路的平均数量的最大可能值。若答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

In the first sample you can put a police station in one of the capitals, then each path will have exactly one safe road. If we place the station not in the capital, then the average number of safe roads will also make .

In the second sample we can obtain the maximum sought value if we put the station in city 4, then 6 paths will have 2 safe roads each, and one path will have 0 safe roads, so the answer will equal .

在第一个样例中，你可以在其中一个首都城市设置一个警察局，这样每条路径将恰好包含一条安全道路。如果我们不在首都城市设置警察局，则安全道路的平均数量也将为 。

在第二个样例中，若将警察局设在第 4 号城市，则可得到所求的最大值：此时有 6 条路径各包含 2 条安全道路，另 1 条路径包含 0 条安全道路，因此答案为 。