D. Баавгай ба мөрдөлт

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

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

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

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

Бэйрланд нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг хотууд болон $m$ ширхэг 2 чиглэлтэй замуудтай байв. $i$-дахь зам нь $a_{i}$ болон $b_{i}$ гэсэн ялгаатай 2 хотыг холбох ба ямар ч 2 зам нь ижил хотуудын хосыг холбоогүй байна. Мөн ямар ч хотоос ямар ч бусад хот уруу хүрэх боломжтой байв (нэг болон нэгээс олон зам ашиглан хүрнэ).

$a$ болон $b$ хотуудын хоорондох зайг $a$ болон $b$ хотуудын хооронд зорчихын тулд шаардагдах замуудын хамгийн цөөн тоогоор тодорхойлох юм.

Лимак бол хүрэн баавгай бөгөөд тэрээр гэмт хэрэгтэн юм. Таны даалгавар бол түүнийг барьж авах эсвэл ядаж түүнийг барьж авах гэж оролдох юм. Танд зөвхөн 2 өдөр (өнөөдөр болон маргааш) байгаа бөгөөд үүнээс хойш Лимак үүрд мөнх нуугдах ажээ.

Таны үндсэн зэвсэг бол БГХИ (баавгай гэмт хэрэгтнийг илрүүлэгч). Та ямар нэгэн хотод байхдаа БГХИ-гээ ашиглаж болох бөгөөд ингэснээр энэ нь танд та болон Лимак-ийн одоо байрлаж байгаа хотын хоорондох зайг хэлж өгөх юм. Харамсалтай нь БГХИ-г нэг өдөрт нэг удаа хэрэглэж болох байв.

Та Лимак-ийн одоогийн байрлалын талаар нэг их зүйл мэдэхгүй боловч та түүнийг $n$ хотуудын аль нэгийг жигд магадлалаар (хот болгонд магадлалтайгаар байх боломжтой) сонгон байрлаж байгаа гэж үзэх юм. Та дараах төлөвлөгөөгөөр ажиллахаар шийджээ:

  1. Нэг хотыг сонгон тэндээ БГХИ-гээ ашиглана.
    • БГХИ-г ашигласны дараа та Лимак-ийг барих гэж оролдох юм (магадгүй энэ нь сайхан санаа биш байж болно). Энэ тохиолдолд та нэг хотыг сонгон тухайн хотыг шалгах юм. Хэрэв Лимак тэр хотод байвал та ялах бөгөөд бусад тохиолдолд Лимак илүү хянамгай болох ба та дахин хэзээ ч түүнийг барьж чадахгүй болох юм (та ялагдана).
  2. Дахин БГХИ-г ашиглахын тулд $24$ цаг хүлээнэ. Та Лимак уг хугацаанд Лимак өөрийн байрлалаа өөрчилнө гэдгийг мэдэж байгаа юм. Тодруулбал тэрээр өөрийн байрлаж буй анхны хотоосоо гарах замуудаас жигд магадлалаар нэг замыг сонгох бөгөөд сонгосон замаа ашиглан өөр хот уруу явах юм.
  3. Маргааш нь та дахин нэг хотыг сонгон тэндээ БГХИ-г ашиглана.
  4. Эцэст нь та Лимак-ийг барих гэж оролдох юм. Та нэг хотыг сонгон тухайн хотыг шалгах юм. Хэрэв Лимак тухайн хотод байвал та ялах бөгөөд бусад тохиолдолд ялагдана.

Та нэг хот сонгох болгондоо $n$ хотуудын аль ч хотыг сонгож болох бөгөөд уг бодлого нь таныг ямар нэгэн газар хурдан очих тухай биш гэдгийг анхаарна уу.

Хэрэв та оновчтой үйлдлүүд хийх бол Лимак-ыг олох магадлал хэд вэ?

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 400$, ) өгөгдөх ба эдгээр нь харгалзан хотуудын тоо болох замуудын тоог илэрхийлнэ.

Дараа нь $m$ мөр өгөгдөнө. Эдгээрийн $i$-дахь мөрөнд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) өгөгдөх бөгөөд энэ нь $i$-дахь замаар холбогдож буй хотуудыг илэрхийлэх юм.

Ямар ч 2 зам нь ижил хотуудын хосыг холбоогүй байх бөгөөд ямар ч хотоос ямар ч бусад хот уруу хүрэх боломжтой байна.

Гаралт

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

Тухайлбал таны хариултын $a$, шүүх хариултыг $b$ гэж үзье. Тэгвэл шалгагч программ нь хэрэв $|a - b| ≤ 10^{ - 6}$ байвал таны хариултыг зөвөөр тооцох юм.

Орчуулсан: Баатархүү

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

Оролт
3 3
1 2
1 3
2 3
Гаралт
0.833333333333
Оролт
5 4
1 2
3 1
5 1
1 4
Гаралт
1.000000000000
Оролт
4 4
1 2
1 3
2 3
1 4
Гаралт
0.916666666667
Оролт
5 5
1 2
2 3
3 4
4 5
1 5
Гаралт
0.900000000000

Тэмдэглэл

Эхний жишээнд 3-н хот байх бөгөөд хос хот болгоны хооронд нэг зам байх юм. Нэгэн оновчтой шийдлийг авч үзье.

  1. $1$-р хотод БГХИ-г хэрэглэнэ.
    • магадлалтайгаар Лимак уг хотод байх бөгөөд БГХИ танд та болон Лимак-ийн байгаа хотын хоорондох зай нь $0$ байна гэж хэлэх юм. Та түүнийг одоо барих гэж оролдох хэрэгтэй бөгөөд ингэснээр ялах нь тодорхой юм.
    • магадлалтайгаар та болон Лимак-ийн байгаа хотын хоорондох зай нь $1$-тэй тэнцүү байх бөгөөд учир нь Лимак $2$ эсвэл $3$-р хотод байх юм. Энэ тохиолдолд та 2-дахь өдрийг хүлээх хэрэгтэй болно.
  2. Та хүлээх ба Лимак өөр хот уруу явах юм.
    • магадлалтайгаар Лимак $2$-р хотод байсан бөгөөд $3$-р хот уруу явсан байх юм.
    • магадлалтайгаар тэрээр $2$-р хотоос $1$-р хот уруу явсан байна.
    • магадлалтайгаар тэрээр $3$-р хотоос $2$-р хот уруу явсан байна.
    • магадлалтайгаар тэрээр $3$-р хотоос $1$-р хот уруу явсан байна.
  3. Бусад өөр хотод ашиглаж болох ч гэсэн $1$-р хотон дахин БГХИ-г ашиглана.
    • Хэрэв та болон Лимак-ийн байгаа хотын хоорондох зай нь $0$ байвал та Лимак-ийг уг хотод байгаад итгэлтэй байх бөгөөд та ялах юм.
    • Хэрэв та болон Лимак-ийн байгаа хотын хоорондох зай нь $1$ байвал Лимак $2$ эсвэл $3$-р хотод байх юм. Дараа нь түүнийг $2$-р хотод ($3$-р хотод байгаа ч гэж таамагласан болно) байгаа гэж таамаглах юм.

Хэрэв Лимак эхлээд $2$-р хотод байсан ба дараа нь тэрээр $3$-р хот уруу явсан тохиолдолд л та ялагдах юм. Ингэснээр таны ялагдах магадлал нь байна. Иймд бодлогын хариулт нь байна.

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