| Codeforces Round 130 (Div. 2) |
|---|
| Закончено |
Дорожная сеть Берляндии состоит из n городов и m двусторонних дорог. Города пронумерованы от 1 до n, причем главная столица имеет номер n, а культурная столица — номер 1. Дорожная сеть устроена таким образом, что по дорогам возможно доехать от любого города до любого другого. Проезд по каждой их дорог в любом направлении занимает одно и тоже время.
Все жители Берляндии — очень ленивые люди, и поэтому, когда они хотят добраться из города v в город u, то всегда выбирают один из кратчайших путей (неважно какой именно).
Правительство Берляндии хочет сделать дорожную сеть своей страны более безопасной и для этого собирается поставить в один из городов пункт полиции, который обладает странным свойством: когда гражданин Берляндии едет по дороге, в одном из концов которой находится пункт полиции, он внимательнее следит за дорогой, и поэтому все такие дороги считаются безопасными. Дороги, оба конца которых отличаются от города с пунктом полиции, считаются опасными.
Теперь Правительство задумалось, где поставить пункт полиции так, чтобы усредненное количество безопасных дорог по всем кратчайшим путям от культурной столицы до главной принимало максимальное значение.
В первой строке входных данных содержатся два целых числа n и m (2 ≤ n ≤ 100, 
) — количество городов и количество дорог в Берляндии соотвественно. Далее в m строках даны пары целых чисел vi, ui (1 ≤ vi, ui ≤ n, vi ≠ ui) — номера городов, соединенных 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
В первом примере если поставить пункт полиции в одну из столиц, тогда на каждом пути будет ровно по одной безопасной дороге, а если пункт поставить не в столицу, то среднее количество безопасных дорог также составит 
.
Во втором примере наибольшее искомое значение достигается, если поставить пункт в город номер 4, тогда 6 путей будут иметь по 2 безопасные дороги, и один путь — 0, таким образом, ответ будет равен 
.
