CF446D DZY Loves Games

Description

Today DZY begins to play an old game. In this game, he is in a big maze with $ n $ rooms connected by $ m $ corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly. DZY has got lost in the maze. Currently he is in the first room and has $ k $ lives. He will act like the follows: - Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked. - Then he will go through the corridor and then the process repeats. There are some rooms which have traps in them. The first room definitely has no trap, the $ n $ -th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the $ n $ -th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

Input Format

N/A

Output Format

N/A