CF446D DZY Loves Games

DZY开始玩一种古老的游戏。 在这个游戏中，他将处于一个巨大的迷宫中，迷宫中有n个房间，由m条走廊相连接（每个走廊允许向两个方向移动）。你可以假设所有房间都直接或间接与走廊相连。 DZY迷失在迷宫中。 目前他在第一个房间，有k条命。 他的行为如下： - 首先，他将随机挑选一条能走出当前所在房间的走廊。 每个走廊被挑选的概率相同。 - 然后，他会穿过走廊，然后重复这个过程。 有些房间里面有陷阱。 第一个房间肯定没有陷阱，但第n个房间肯定有一个陷阱。 每当DZY进入其中一个房间时，他就会失去一条命。 如果他进入第n个房间，只有2条命的话，首先他将失去一条生命，但随后他将进入奖金回合。 他想知道他进入奖金回合的可能性有多大。 ## 输入输出：

无

无