토너먼트

어느 도시에서 격투기 토너먼트가 열린다. 참가자는 모두 $N$명이며, 그중 두 명은 형제인 올렉(Olek)과 펠렉(Felek)이다.

모든 경기는 두 참가자가 맞붙어 치르며, 승자 한 명만 토너먼트에 남고 패자는 탈락한다. 경기가 치러지는 순서는 대회 전에 "토너먼트 대진표"로 미리 정해져 있다. 아래 그림은 참가자가 4명일 때의 대진표 예시로, 노란색 칸에서 참가자가 "출발"하고 초록색 칸은 경기를 나타낸다.

대회가 시작될 때 참가자들은 출발 위치에 균등한 확률로 무작위 배정되며, 참가자를 노란색 칸에 배치하는 모든 방법은 서로 같은 확률로 나타난다.

올해는 실력이 매우 평준화되어 있어, 각 경기는 맞붙은 두 참가자가 각각 $\frac{1}{2}$의 확률로 이긴다고 가정한다.

토너먼트가 진행되는 동안 형제인 올렉과 펠렉이 서로 맞붙게 될 확률을 구하여라.

첫 줄에는 테스트 묶음의 개수 $Z$ ($1 \le Z \le 5$)가 주어진다. 이어서 각 묶음의 설명이 차례로 주어진다.

각 묶음은 참가자 수를 나타내는 정수 $N$ ($2 \le N \le 1000$)으로 시작한다. 그 뒤로 $1$번부터 $N-1$번까지 번호가 매겨진 $N-1$개의 경기 설명이 한 줄에 하나씩 주어진다.

각 경기 설명은 공백 하나로 구분된 두 개의 문자열로 이루어지며, 각 문자열은 그 경기에 나서는 두 참가자 중 하나를 가리킨다.

• Z<k> (예: Z1, Z4, $1 \le k \le N$)는 출발 위치 $k$에 배정된 참가자를 뜻한다.
• P<k> (예: P1, P4, $1 \le k \le N-1$)는 $k$번 경기의 승자를 뜻한다.

입력은 항상 올바른 대진표를 이룬다. 즉, 모든 출발 위치는 정확히 한 경기에 들어가고, 마지막 경기를 제외한 모든 경기의 승자는 정확히 하나의 이후 경기에 들어간다.

각 묶음마다 올렉과 펠렉이 서로 맞붙게 될 확률을 한 줄에 하나씩 출력한다. 값은 소수점 아래 정확히 넷째 자리까지 반올림하여 출력하며, 반올림 시 정확히 $0.5$인 자리는 올린다. (예: 0.5000)