P13794 [SWERC 2023] Metro quiz

:::align{center}  ::: 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 $\texttt{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 \texttt{not possible} (in lowercase characters). Answers within $10^{-4}$ of the correct answer will be accepted.

**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$.