Pass the Buck

Pass the Buck 게임에는 여러 명의 플레이어가 있고, 각 플레이어는 다른 플레이어 중 한 명 이상을 이웃으로 가진다.

각 게임은 무작위로 한 명의 플레이어를 선택해 그 플레이어가 버크(buck)를 받는 것으로 시작한다(이 게임에서 무작위란 모든 결과가 같은 확률로 나온다는 뜻이다).

이후 각 단계에서 현재 버크를 가진 플레이어의 이웃이 d명이면, 그 플레이어는 [0, d] 범위의 정수 k를 무작위로 고른다. 0을 고르면 현재 소지자가 우승자가 되어 버크를 가진다. 그렇지 않으면 소지자는 k번째 이웃에게 버크를 넘기고, 그 이웃이 새 소지자가 된다.

게임은 어떤 소지자가 우승할 때까지 계속된다.

플레이어 k가 첫 소지자일 때 플레이어 j가 우승할 확률을 구하는 프로그램을 작성하라.

플레이어와 이웃의 배치는 플레이어를 정점으로, 두 플레이어가 이웃이면 두 정점 사이에 간선이 있는 그래프로 나타낼 수 있다. 예를 들어 한 줄로 앉아 있다면 이웃은 왼쪽과 오른쪽의 플레이어이다(있는 경우에 한한다).

둥근 탁자에 둘러앉아 있다면 각 플레이어는 오른쪽과 왼쪽에 이웃이 하나씩 있다.

여러 줄로 앉아 있다면 왼쪽, 오른쪽, 앞, 뒤에 이웃이 있을 수 있다.

입력은 여러 줄로 이루어진다. 첫 줄에는 플레이어 수 N(2 <= N <= 20)이, 그 뒤에 공백 하나를 두고 시작/우승 쌍의 수 P(1 <= P <= 20)가 주어진다.

다음 N개 줄에는 각 플레이어의 이웃이 주어진다. m번째 줄은 플레이어 m의 이웃을 나타낸다. 줄의 첫 정수는 플레이어 m의 이웃 수 d(m)이다. 그 뒤에 m의 이웃들의 번호 d(m)개가 공백으로 구분되어 주어진다.

다음 P개 줄에는 시작 소지자의 번호 s와, s가 첫 소지자일 때 우승 확률을 구할 플레이어의 번호 w가 주어진다. 각 줄에는 쌍의 번호 j, s(j), w(j) 세 정수가 공백으로 구분되어 주어진다.

프로그램은 P개 줄을 출력한다.

j번째 줄에는 정수 j와 공백 하나, 그리고 플레이어 s(j)가 첫 소지자일 때 플레이어 w(j)가 우승할 확률을 소수점 다섯 자리로 나타낸 값을 출력한다.