시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 2 1 100.000%

문제

W pewnym mieście odbywa się turniej sztuk walki. Startuje w nim N zawodników, z czego dwóch stanowią bracia - Olek i Felek.

W turniejowych pojedynkach bierze udział po dwóch zawodników i każdy pojedynek ma jednego zwycięzce, który pozostaje w turnieju, podczas gdy przegrany odpada. Układ pojedynków ilustruje "drzewo turniejowe" ustalane przed zawodami. Poniżej prezentujemy przykładowe drzewo turniejowe dla turnieju z czterema zawodnikami. W żółtych polach "zaczynają" zawodnicy, zielone pola oznaczają pojedynki.

Na początku turnieju zawodnicy rozlosowywani są po pozycjach startowych, i każde przyporządkowanie zawodników do żółtych pól jest tak samo prawdopodobne.

Co więcej, w tym roku poziom jest tak wyrównany, że należy przyjąć, że każdy pojedynek z równym prawdopodobieństwem zostanie wygrany przez każdego z dwóch biorących w nim udział zawodników.

Oblicz prawdopodobieństwo, że w toku turnieju bracia Olek i Felek będą ze sobą walczyć.

입력

W pierwszej linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 5 ). Następnie podawane są opisy kolejnych zestawów.

Opis zestawu rozpoczyna się od liczby naturalnej N ( 2 <= N <= 1000 ) określającej liczbę zawodników w turnieju. Następnie podawane są opisy wszystkich N-1 pojedynków turniejowych ( numerowanych kolejno od 1 do N-1 ), po jednym w linii.

Opis pojedynku składa się z dwóch oddzielonych spacją ciągów znaków, każdy z nich opisuje jednego z zawodników walczących w pojedynku.

  • Zliczba ( np. Z1, Z4, etc, 1 <= liczba <= N ) oznacza zawodnika na pozycji startowej liczba.
  • Pliczba ( np. P1, P4, etc, 1 <= liczba <= N-1 ) oznacza zawodnika, który zwycięży w pojedynku o numerze liczba.

Można przyjąć, że opis tworzy poprawne drzewo turniejowe, tj. każda pozycja startowa przypisana jest dokładnie do jednego pojedynku i zwycięzca każdego pojedynku poza jednym przypisany jest do dokładnie jednego pojedynku.

출력

Dla każdego zestawu należy wypisać w osobnej linii prawdopodobieństwo, że w Olek z Felkiem będą ze sobą walczyć z dokładnością do 0.0001.

예제 입력 1

1
4
P2 Z4
P3 Z1
Z2 Z3

예제 출력 1

0.5

출처

Contest > Spot > HotSpot 2010 3-1번