Rainbow Island

Recently, a new emerging game has become popular in Hogwarts.

The goal of the game is to connect all islands in the ground with rainbows. At the beginning, n islands are isolated and the player arrive at the first island. There is a red magic set and a blue magic set on each island. Once the players of the game arrive at one of the islands, they will follow the sequence, which is firstly entering the red magic set, then the blue one. When a player enters the red magic set, he/she has the possibility of p to gain a rainbow, thereby two random island of all will be connected by the rainbow(including which two have been connected). When a player enters the blue magic set, he/she will be sent to one of the s islands with same possibility. One unit of total magic volume will be expended when the player uses the blue magic. At the end of the game, the winner is the one who consumes the least of total magic volume.

However, the brilliant Hermione despises the game, she wants to know the expected magic volume to be taken away the goal of the game was achieved.

There are multiply test cases.

The first line contains an integer T(T<=100), indicates the number of cases.
For each case the first line contains an integer n, indicates the number of the islands. (1<=n<=20)

Then there will be n numbers, pi indicates the possibility to gain a rainbow for the i-th island. (0<pi<1)

The next n lines, each line firstly contains an integer s, then followed by s integers, indicates the number of which the i-th island can arrive at. (1 <= s <= n)

For each test case, you should output “Case #K: “ first, where K indicates the case number and counts from 1. Then output the answer. Round the answer to the sixth digit after the decimal point.

2
3
0.123 0.984 0.63
2 1 2
2 2 3
2 1 3
2
0.75 0.34
2 1 2
2 1 2

Case #1: 4.931167
Case #2: 1.458716

If the player achieve the goal of the game, he/she won't enter the blue magic set anymore.

UESTC

2014 Multi-University Training Contest 7