#1871. JC的小苹果

JC的小苹果

Description

让我们继续JC和DZY的故事。

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

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

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

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

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

Format

Input

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

Output

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

Samples

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

Limitation

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