여름 합숙의 아침은 이르다

면접 대비

시간 제한8초메모리 제한512 MB

요약

각 참가자가 늦잠잘 확률과 연락처 방향 그래프가 주어질 때, 깨어 있는 참가자의 전화로 모두가 깨어날 확률을 구한다.

난이도: 보통10점 중 7점
유형: 확률, 그래프, BFS, 비트 연산
정답자: 아직 제출이 없습니다

문제

JAG 여름 합숙의 아침은 이르다. 정확히는 그렇게까지 이르지는 않지만, 이르다고 느끼는 참가자가 많다고 한다.

해마다 합숙 장소로 쓰이는 시설에서는 퇴실할 때 참가자가 시트 회수와 청소를 해야 한다. 한 방이라도 퇴실이 늦어지면 이후 시설 이용에 문제가 생기므로, 참가자는 단 한 명도 늦잠을 자면 안 된다.

그렇다고 해도 사람인지라 늦잠을 잘 수도 있다. 그러나 일어난 사람이 연락처를 아는 사람에게 모닝콜을 걸면, 아무도 늦잠을 자지 않도록 할 수 있을 것이다.

JAG 여름 합숙 운영을 맡은 당신은 늦잠을 반드시 막을 대책을 세우기 위한 사전 준비로, 어느 정도의 확률로 전원이 제때 일어날 수 있는지 조사하기로 했다. 준비로 우선 각 참가자가 늦잠을 잘 확률과 각자가 연락처를 아는 사람의 목록을 입수했다. 여기서 방은 개인실이므로, 각자가 늦잠을 자는지 여부는 다른 참가자가 늦잠을 자는지 여부와 독립이다. 일어난 사람은 반드시 아는 모든 연락처에 모닝콜을 걸고, 모닝콜을 받은 사람은 반드시 일어난다고 가정할 때, 전원이 제때 일어날 확률을 이 정보로부터 계산하라.

입력

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

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

N은 참가자의 수이며, 100을 넘지 않는 양의 정수이다. pi는 i번째 참가자가 늦잠을 잘 확률이며, 소수점 이하 2자리 이내의 0 이상 1 이하인 실수이다. mi는 i번째 참가자가 아는 연락처의 수이며, 0 이상 N 이하인 정수이다. a(i, j)는 i번째 참가자가 아는 j번째 연락처가 a(i, j)번째 참가자의 것임을 나타낸다. a(i, j)는 N을 넘지 않는 양의 정수이다.

입력의 끝은 0 하나로 이루어진 줄로 나타낸다.

출력

각 데이터 세트에 대해 전원이 기상할 수 있는 확률을 한 줄에 출력하라. 출력에는 0.00001 이상의 오차가 있어서는 안 된다.

예제1

예제 1

입력

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

예상 출력

0.400000000
0.640000000
0.998800000
0.168000000
0.900000000
0.792000000
0.151200000