Summer Camp Mornings Come Early

Interview

Time limit8sMemory limit512 MB

Summary

Given each participant's independent oversleeping probability and a directed contact graph, find the probability that calls from awake participants eventually wake everyone.

Level: Medium7 of 10
Topics: Probability, Graph, BFS, Bit manipulation
Solved: No attempts yet

Problem

Mornings at the JAG summer camp come early. To be precise, not that early, but many participants feel they do.

The facility that hosts the camp every year requires participants to collect sheets and clean up when they leave. If even one room is late to check out, it affects the use of the facility in later years, so not a single participant may oversleep.

Even so, everyone is human, and people sometimes oversleep. However, if those who are awake call the people whose contact information they know, it should be possible to make sure no one oversleeps.

Put in charge of running the JAG summer camp, you decided to investigate how likely it is that everyone wakes up properly, as preparation for measures that will absolutely prevent oversleeping. As preparation, you first obtained each participant's probability of oversleeping and the list of people whose contact information each participant knows. Here, since the rooms are private, whether each person oversleeps is independent of whether the other participants oversleep. Assuming that anyone who is awake always calls everyone whose contact information they know, and that anyone who receives a call always wakes up, compute from this information the probability that everyone wakes up properly.

Input

The input consists of multiple datasets. Each dataset has the following format.

N
p1 m1 a(1,1) ... a(1, m1)
...
pN mN a(N,1) ... a(N, mN)

N is the number of participants, a positive integer not exceeding 100. pi is the probability that the i-th participant oversleeps, a real number between 0 and 1 inclusive with at most 2 digits after the decimal point. mi is the number of contacts the i-th participant knows, an integer between 0 and N inclusive. a(i, j) means that the j-th contact known to the i-th participant belongs to the a(i, j)-th participant. a(i, j) is a positive integer not exceeding N.

The end of the input is indicated by a line consisting of a single zero.

Output

For each dataset, output the probability that everyone can wake up on one line. The output must not contain an error of 0.00001 or more.

Examples1

Example 1

Input

2
0.60 1 2
0.60 0
2
0.60 1 2
0.60 1 1
5
0.10 1 2
0.20 1 3
0.30 1 4
0.40 1 5
0.50 1 1
5
0.10 0
0.20 1 1
0.30 1 1
0.40 1 1
0.50 1 1
5
0.10 4 2 3 4 5
0.20 0
0.30 0
0.40 0
0.50 0
4
0.10 1 2
0.20 0
0.30 1 4
0.40 1 3
5
0.10 0
0.20 0
0.30 0
0.40 0
0.50 0
0

Expected output

0.400000000
0.640000000
0.998800000
0.168000000
0.900000000
0.792000000
0.151200000