#3640. JC的小苹果

内存限制:256 MiB 时间限制:15 Sec

题目描述

   让我们继续JCDZY的故事。

    “你是我的小丫小苹果,怎么爱你都不嫌多!”

    “点亮我生命的火,火火火火火!”

    话说JC历经艰辛来到了城市B,但是由于他的疏忽DZY偷走了他的小苹果!没有小苹果怎么听歌!他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC1号点,他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。

    但是JC迷路了,他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的,一共有m条,怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。

    P.S.大家都知道这个系列是提高组模拟赛,所以这是一道送分题balabala

输入格式

第一行三个整数表示nmhp。接下来一行整数,第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数ab表示ab间有一条无向边。

输出格式

    仅一行,表示JC找到他的小苹果的期望概率,保留八位小数。

样例

样例输入


			
3 3 2
0 1 0
1 2
1 3
2 3

样例输出


			
0.87500000

数据范围与提示

对于100%的数据 2<=n<=150,hp<=10000,m<=5000,保证图联通。