C. Цагдаагийн газар

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландын замын сүлжээнд $n$ хот болон хоёр чиглэлт $m$ зам байдаг. Хотууд $1$-с $n$ хүртэл дугаарлагдсан бөгөөд нийслэл хот $n$ дугаартай, соёлын нийслэл $1$ дугаартай гэнэ. Замын сүлжээ нь аль ч хотоос аль ч хотруу хүрэх боломжтой байхаар зохион байгуулагдсан ба аль ч замаар зорчиход тогтмол хугацаа зарцуулдаг.

Берландын бүх иргэд маш залхуу болохоор $v$ хотоос $u$ хотруу зорчих үедээ үргэлж хамгийн богино замаар явдаг (олон богино зам байвал дурын нэгээр нь) байна.

Берландын засгийн газар замаар зорчих үеийн аюулгүй байдлыг өндөржүүлхийн тулд нэг хотод цагдаагийн хэсэг нээхээр шийджээ. Берландын иргэд явж буй замынх нь аль нэг төгсгөлийн хотод нь цагдаагийн газар байрладаг бол тэр замаар удаан явдаг гэнэ. Ийм учир уг замыг аюулгүй зам гэж үзэж болно. Харин аль ч төгсгөлд нь цагдаагийн хэсэг байрладаггүй замыг аюултай зам гэж үзнэ.

Засгийн газрынхан аль хотод цагдаагийн хэсэг байгуулвал нийслэл хотоос соёлын нийслэлрүү явах бүх боломжит замын хувьд дундаж аюулгүй замын тоо хамгийн их байхыг мэдэхийг хүссэн.

Оролт

Оролтын эхний мөрөнд Берландын хотын тоо болон замын тоо $n$, $m$ () байна. Дараагийн $m$ мөр бүрт $i$-р хотоор холбогдсон хоёр хотын индекс $v_i$, $u_i$ ($1 ≤ v_i, u_i ≤ n$, $v_i ≠ u_i$) өгөгдөнө.

Өгөгдөлд аль ч хоёр хот хоорондоо нэгээс олон замаар холбогдоогүй ба аль ч хотоос аль ч хотруу очих боломжит зам оршин байна.

Гаралт

Аль ч хамгийн богино замаар 2 нийслэлийн хооронд явах үед дайрч өнгөрөх дундаж аюулгүй замын тоог хэвлэ. Хариу абсолют утгаараа $10^{-6}$-с ихгүй зөрүүтэй байвал зөв гэж үзнэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
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

Тэмдэглэл

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 .

Сэтгэгдлүүдийг ачааллаж байна...