Сегодня DZY играет в очень старую компьютерную игру. В этой игре он находится в большом лабиринте с n комнатами, соединенными m коридорами (по каждому коридору можно ходить в обоих направлениях). При этом между любыми двумя комнатами существует путь, проходящий по коридорам.
DZY потерялся в лабиринте. Сейчас он находится в первой комнате, и у него есть k жизней. Он будет действовать следующим образом:
- Сперва юноша равновероятно выбирает один из коридоров, выходящих из его текущей комнаты.
- Затем он идет по этому коридору, после чего процесс повторяется.
В некоторых комнатах расставлены ловушки. Гарантируется, что в первой комнате ловушек нет, а в n-й комнате ловушка есть. Каждый раз, когда DZY входит в одну из комнат с ловушкой, он теряет одну жизнь. DZY знает, что если он войдет в n-ю комнату ровно с 2 жизнями, то сначала он потеряет одну жизнь, но затем попадет на бонусный уровень. Юноша хочет знать вероятность того, что он попадет на бонусный уровень. Пожалуйста, помогите ему.
Выходные данные
Выведите единственное вещественное число — вероятность того, что DZY попадет на бонусный уровень. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превосходит 10 - 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 3
0 0 1 0 1
1 2
2 3
3 4
4 5
1 2
|
0.25000000
|
|
2
|
3 2 2
0 1 1
1 2
2 3
|
-0.00000000
|
|
3
|
2 1 3
0 1
1 2
|
1.00000000
|