D. Дзи тоглоомуудад дуртай

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

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

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

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

Өнөөдөр Дзи хуучин тоглоомоо тоглож эхэлж байна. Энэ тоглоомонд тэр $m$ хонгилоор холбогдсон $n$ өрөөнүүдтэй том төөрдөг байшинд байна (хонгил бүрээр хоёр чиглэлд шилжих боломжтой). Бүх өрөөнүүд нь шууд ба шууд бус хонгилоор холбогдсон гэж үзье.

Дзи төөрдөг байшинд төөрсөн байна. Одоо тэр эхний өрөөнд байгаа ба түүнд $k$ амь байна. Тэр дараах байдлаар ажиллана:

  • Эхлээд тэр хонгилуудаас санамсаргүйгээр нэгийг нь сонгоод одоо байгаа өрөөнөөсөө явна. Гаралт бүр нь тэнцүү магадлалтай сонгогдоно.
  • Дараа нь тэр хонгилоор явах ба энэ үйлдэл давтагдана.

Зарим өрөөнүүдэд занга байгаа. Эхний өрөөнд мэдээж занга байхгүй, $n$-р өрөөнд занга байгаа. Дзи эдгээр өрөөнүүдийн нэгэнд орох бүрд нэг амь хасагдана. Хэрвээ тэр $n$-р өрөөнд яг 2 амьтай орвол, эхлээд нэг амиа алдах боловч дараа нь бонус үеийг нээх болно гэдгийг тэр мэддэг. Тэр бонус үеийг нээх магадлалыг мэдэхийг хүсэж байна. Түүнд туслана уу.

Оролт

Эхний мөр нь $n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 10^{5}; 2 ≤ k ≤ 10^{9})$ гурван бүхэл тоог агуулна.

Хоёр дахь мөр нь $n$ бүхэл тоонуудыг агуулах ба эдгээр нь $0$ эсвэл $1$ байна. Хэрвээ $i$-р тоо нь $1$ бол $i$-р өрөөнд занга байгаа, эсрэг тохиолдолд занга байхгүй. Зангатай өрөөнүүдийн тоо $101$-с илүүгүй гэдгийг анхаарна уу. Эхний өрөөнд занга байхгүй, $n$-р өрөөнд занга байгаа гэдэг нь баталгаатай юм.

Дараа нь $m$ мөрүүд байгаа. Мөр бүр нь $u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i})$ хоёр бүхэл тоог агуулах ба эдгээр нь одоогийн байгаа $u_{i}$ ба $v_{i}$ өрөөнүүдийг холбосон хонгил юм. Хонгилын систем нь холбогдсон байна.

Гаралт

Нэг бодит тоо л хэвлэнэ. Энэ нь Дзигийн бонус үеийг нээх магадлал юм. Хэрвээ харьцангуй буюу үнэмлэхүй алдаа нь $10^{ - 4}$-с хэтрээгүй бол хариултыг зөв гэж үзэж болно.

Орчуулсан: Даариймаа

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

Оролт
5 5 3
0 0 1 0 1
1 2
2 3
3 4
4 5
1 2
Гаралт
0.25000000
Оролт
3 2 2
0 1 1
1 2
2 3
Гаралт
-0.00000000
Оролт
2 1 3
0 1
1 2
Гаралт
1.00000000
Сэтгэгдлүүдийг ачааллаж байна...