Identifying the Assassin

There is a cold‐blooded assassin who has infiltrated Na-wiat by disguising as an ordinary civilian. The police know that among N people exactly one is the assassin, and each person has equal probability to be the assassin. Using the information of who knows whom, the police can interrogate people. When interrogating a civilian, the civilian truthfully reports, for each person he knows, whether that person is the assassin (if he knows) or a civilian. However, if the police interrogate the assassin, the assassin will kill the police officer immediately.

The police want to design a strategy that guarantees their own safety (i.e. they never interrogate the assassin) and enables them to determine exactly who the assassin is. The strategy is as follows. The police choose a set T of people to interrogate, leaving the remainder set S un-interrogated. They must have that for every person v in S there exists at least one person u in T such that u knows v (so that if v turns out to be the assassin, the testimony from u will reveal it). Since interrogating a person risks death if that person is the assassin, the police will be safe only if the assassin belongs to S. With the knowledge that the assassin is chosen uniformly at random from all people, the probability of success is
\[ P = \frac{|S|}{N} = \frac{N - |T|}{N}, \]

where T is any set that dominates the remaining vertices in the sense that for every v not in T (i.e. in S) there exists some u in T with an edge from u to v (here an edge indicates that u knows v).

The goal is to choose T as small as possible (or equivalently, choose S as large as possible) so as to maximize P. Formally, given the directed graph defined by the acquaintances (for each person i, you are given the list of persons that i knows), find the minimum-size dominating set T such that for every person v in \(S = V \setminus T\) there exists some u in T with an edge from u to v. Then output the maximum guaranteed success probability:

[ P_{max} = \frac{N - |T|}{N}. ]

Note: For the purpose of this problem, assume that the number of people N is small (for example, \(N \le 20\)), so that an exponential search (using bit masks) is acceptable.

inputFormat

The first line contains an integer N (\(1 \le N \le 20\)), the number of people. Each of the following N lines describes one person. The i-th line starts with an integer k indicating the number of people that person i knows, followed by k space‐separated integers representing the IDs of the people that person i knows. The people are numbered from 1 to N.

outputFormat

Output a floating point number representing the maximum probability (with at least 6 decimal places) that the police remain safe and correctly identify the assassin under the optimal strategy.

sample

2
1 2
1 1

0.500000