B"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: 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. The first line contains three integers n, xe2 x80 x89m, xe2 x80 x89k (2 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89500; 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105; 2 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89k xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109). The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap. Then m lines follows. Each of them contains two integers ui, xe2 x80 x89vi (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ui, xe2 x80 x89vi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n; ui xe2 x80 x89 xe2 x89 xa0 xe2 x80 x89vi), meaning that current corridor connects two rooms ui and vi. It is guaranteed that the corridor system is connected. Print the only real number -- the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 xe2 x80 x89- xe2 x80 x894."...