Turniej

Turniej

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów

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ć.

Wejście

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.

Wyjście

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.

Przykład

Przykład odpowiada rysunkowi z treści.