今天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,则认为答案是正确的。
示例
输入 #1
5 5 3 0 0 1 0 1 1 2 2 3 3 4 4 5 1 2
输出 #1
0.25000000
输入 #2
3 2 2 0 1 1 1 2 2 3
输出 #2
-0.00000000
输入 #3
2 1 3 0 1 1 2
输出 #3
1.00000000