AlgoLiga 2018

"50% Polaków nie zdaje sobie sprawy,

że stanowi połowę społeczeństwa"

miesięcznik Nowy Pompon

Bajtek pracuje dla pewnego bajtockiego banku jako analityk. Został właśnie poproszony o sporządzenie raportu dotyczącego bezpieczeństwa jego zasobów. Bank ten, z pewnych względów, ma dość specyficzny system. Znajduje się w nim bowiem n sejfów. W każdym z nich są pewne zasoby oraz klucz do któregoś z n sejfów, za pomocą którego dany sejf można otworzyć. Wiadomo, że każdy z tych n kluczy pasuje do innego sejfu. Bajtek znając zawartość każdego z sejfów musi umieć szybko odpowiadać na pytanie: ile minimalnie sejfów należy otworzyć, aby korzystając z ich zawartości móc otworzyć wszystkie pozostałe? Po chwili namysłu stwierdził, że nie będzie to takie straszne zadanie. Kiedyś już chyba coś podobnego pisał, albo może nawet coś trudniejszego.

Niestety to nie koniec analizy. Zarząd banku zażyczył sobie również inne dane. Jest ciekaw jakie, zmieniając ustawienie kluczy w sejfach na losowe oraz otwierając k losowych sejfów, jest prawdopodobieństwo tego, że uda się otworzyć wszystkie pozostałe sejfy. Na takie pytania Bajtek też musi być gotowy.

Wejście

Wejście rozpoczyna liczba testów 0<t<=100. Każdy test składa się kolejno z liczby 0<n<=1000 oraz n liczb całkowitych ze zbioru {1, ..., n}. i-ta z tych liczb to numer sejfu do którego klucz znajduje się w i-tym sejfie. Następnie jest liczba 0<q<=1000 oznaczająca liczbę zapytań. Każde zapytanie składa się z jednej liczby całkowitej 0<=k<=n.

Wyjście

Dla każdego testu należy wypisać odpowiedź w postaci najmniejszej liczby sejfów które należy otworzyć, aby korzystając z ich zawartości móc otworzyć wszystkie pozostałe oraz odpowiedź na każde zapytanie w oddzielnej linii. Odpowiedzią na zapytanie jest prawdopodobieństwo, że otworzywszy k sejfów uda nam się otworzyć pozostałe n-k sejfów (przy losowym rozmieszczeniu kluczy), wypisane z dokładnością do czterech cyfr po kropce dziesiętnej.

Przykład

Wejście:
2
3
2 1 3
1
1
5
2 1 3 5 4
2
0
5

Wyjście:
2
0.3333
3
0.0000
1.0000