CF446D DZY Loves Games

DZY 开始玩一种古老的游戏。在这个游戏中，他将处于一个巨大的迷宫中，迷宫中有 $n$ 个房间，由 $m$ 条走廊相连接（每个走廊允许**双向移动**）。 DZY 迷失在迷宫中。目前他在第一个房间，有 $k$ 条命。他的行为如下： - 首先，他将随机挑选一条能走出当前所在房间的走廊。每个走廊被挑选的概率**相同**。 - 然后，他会穿过走廊走到一个新房间，然后重复这个过程。 有些房间里面有陷阱。第一个房间一定没有陷阱，且第 $n$ 个房间一定有陷阱。 每当 DZY 进入其中一个**有陷阱的**房间时，他就会失去一条命。当他进入第 $n$ 个房间（即有宝箱的房间）时： - 若 DZY 还剩 $2$ 条命，则直接获胜。 - 若剩余不到 $2$ 条命，则游戏失败。 DZY 想知道他获胜的概率是多少。

第一行包含三个整数 $n,m,k$，含义如题所述。 第二行包含 $n$ 个整数，每个数均为 $0$ 或 $1$。第 $i$ 个数为 $1$ 则代表第 $i$ 个房间有陷阱，否则代表该房间没有陷阱。输入数据保证第 $1$ 个房间无陷阱，第 $n$ 个房间有陷阱。 接下来 $m$ 行，每行两个整数 $u_j,v_j(1 \le j \le m,1 \le u_j,v_j \le n,u_j \neq v_j)$ 表示第 $j$ 条走廊连接了编号为 $u_j,v_j$ 的房间。数据保证整个迷宫是联通的。

一行一个实数，表示 DZY 获胜的概率，误差不超过 $10^{-4}$ 即为通过。

对于 $100\%$ 的数据，保证 $2 \le n \le 500,1 \le m \le 10^5,2 \le k \le 10^9$，且有陷阱的房间数不超过 $101$ 个。