Two Olympics spectators are waiting in a queue. They each hold a copy of the metro map of Paris, and they devised a little game to kill time. First, player A thinks of a metro line (chosen uniformly at random among all metro lines) that player B will need to guess. In order to guess, player B repeatedly asks whether the line stops at a metro station of her choice, and player A answers truthfully. After enough questions, player B will typically know with certainty which metro line player A had in mind. Of course, player B wants to minimise the number of questions she needs to ask.
You are given the map of the $$$M$$$ metro lines (numbered from 1 to $$$M$$$), featuring a total of $$$N$$$ metro stations (numbered from 0 to $$$N-1$$$) and indicating, for each line, those stations at which the line stops. Please compute the expected number of questions that player B needs to ask to find the answer, in the optimal strategy.
In other words, given a strategy $$$S$$$, note $$$Q_{S,j}$$$ the number of questions asked by the strategy if the metro line in the solution is line $$$j$$$. Then, note $$$$$$ E_S = \mathbb{E} \left[ Q_S \right] = \frac{1}{M} \sum_{j = 1}^M Q_{S, j} $$$$$$ the expected value of $$$Q_{S,j}$$$ assuming that $$$j$$$ is uniformly chosen from the set of all metro lines. Your task is to compute $$$\min_S E_S$$$.
If it is not always possible for player B to know which line player A had in mind with certainty, output not possible.
The first line contains the number $$$N$$$. The second line contains the number $$$M$$$. Then follow $$$M$$$ lines: the $$$k^\text{th}$$$ such line contains first a positive integer $$$n \leq N$$$, then a space, and then $$$n$$$ space-separated integers $$$s_1 , s_2 , \dots, s_n$$$ ; these are the metro stations at which line $$$k$$$ stops. A line stops at a given station at most once.
Limits
- $$$1 \leq N \leq 18$$$;
- $$$1 \leq M \leq 50$$$.
The output should contain a single line, consisting of a single number: the minimum expected number of questions that player B must ask in order to find the correct metro line, or not possible (in lowercase characters). Answers within $$$10^{-4}$$$ of the correct answer will be accepted.
5 4 3 0 3 4 3 0 2 3 3 2 3 4 2 1 2
2
3 3 1 0 1 1 1 2
1.66666666666667
Sample Explanation 2
Ask the first question about station 0: this is optimal by symmetry of the problem. This lets us distinguish between line 1, which stops at station 0, and lines 2 and 3, which do not. If needed, ask a second question to distinguish between lines 2 and 3. Player B asks one question if the answer is line 1, and two questions otherwise. Thus, the expected number of questions she will ask is $$$(1 + 2 \times 2)/3$$$.
