D. DZY любит игры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня DZY играет в очень старую компьютерную игру. В этой игре он находится в большом лабиринте с n комнатами, соединенными m коридорами (по каждому коридору можно ходить в обоих направлениях). При этом между любыми двумя комнатами существует путь, проходящий по коридорам.

DZY потерялся в лабиринте. Сейчас он находится в первой комнате, и у него есть k жизней. Он будет действовать следующим образом:

  • Сперва юноша равновероятно выбирает один из коридоров, выходящих из его текущей комнаты.
  • Затем он идет по этому коридору, после чего процесс повторяется.

В некоторых комнатах расставлены ловушки. Гарантируется, что в первой комнате ловушек нет, а в n-й комнате ловушка есть. Каждый раз, когда DZY входит в одну из комнат с ловушкой, он теряет одну жизнь. DZY знает, что если он войдет в n-ю комнату ровно с 2 жизнями, то сначала он потеряет одну жизнь, но затем попадет на бонусный уровень. Юноша хочет знать вероятность того, что он попадет на бонусный уровень. Пожалуйста, помогите ему.

Входные данные

В первой строке записано три целых числа n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

Во второй строке записано n целых чисел, каждое из них равняется 0 или 1. Если i-е число равняется 1, значит, в i-й комнате находится ловушка. В противном случае ловушки в комнате нет. Обратите внимание, что количество комнат с ловушками не превышает 101. Гарантируется, что в первой комнате ловушек нет, а в n-й комнате ловушка есть.

Затем следует m строк. В каждой строке записано по два целых числа ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), которые обозначают, что текущий коридор соединяет две комнаты, ui и vi. Гарантируется, что система коридоров связная.

Выходные данные

Выведите единственное вещественное число — вероятность того, что DZY попадет на бонусный уровень. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превосходит 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