P13794 [SWERC 2023] Metro quiz

:::align{center}  ::: 两位奥运观众正在排队。他们每人手里都有一份巴黎地铁线路图，为了打发时间，他们想出了一个小游戏。首先，玩家 A 会在所有地铁线路中随机选择一条地铁线路（每条线路被选中的概率相同），让玩家 B 猜是哪一条。为了猜测，玩家 B 可以反复询问某个地铁站是否有该线路停靠，玩家 A 会如实回答。在经过足够多的提问后，玩家 B 通常可以确定玩家 A 想到的是哪一条地铁线路。当然，玩家 B 希望她需要提问的次数尽可能少。 现在给定 $M$ 条地铁线路（编号为 $1$ 到 $M$）的地铁线路图，共有 $N$ 个地铁站（编号为 $0$ 到 $N-1$），并给出每条线路停靠的地铁站。请你计算，在最优策略下，玩家 B 需要提问的期望次数。 换句话说，给定一个策略 $S$，记 $Q_{S,j}$ 表示如果答案是第 $j$ 条地铁线路时，按照策略 $S$ 需要提问的次数。那么 $$ E_S = \mathbb{E} \left[ Q_S \right] = \frac{1}{M} \sum_{j = 1}^M Q_{S, j} $$ 表示在第 $j$ 条线路等概率被选中的情况下，$Q_{S,j}$ 的期望值。你的任务是计算 $\min_S E_S$。 如果玩家 B 无法总是确定玩家 A 想到的是哪一条线路，请输出 $\texttt{not possible}$。

第一行包含一个整数 $N$，表示地铁站的数量。 第二行包含一个整数 $M$，表示地铁线路的数量。 接下来 $M$ 行，每行描述一条地铁线路：第 $k$ 行首先是一个正整数 $n \leq N$，表示该线路停靠的地铁站数量，接着是 $n$ 个用空格分隔的整数 $s_1, s_2, \dots, s_n$，表示该线路停靠的地铁站编号。每条线路在同一个地铁站最多停靠一次。 **数据范围** - $1 \leq N \leq 18$； - $1 \leq M \leq 50$。

输出一行，包含一个数字，表示玩家 B 至少需要提问的期望次数，或者输出 \texttt{not possible}（小写字母）。如果你的答案与正确答案的误差不超过 $10^{-4}$，则视为正确。

**样例解释 2** 第一次询问地铁站 $0$，由于问题具有对称性，这是最优的。这样可以区分停靠站 $0$ 的线路 $1$ 和不在站 $0$ 停靠的线路 $2$、$3$。如果需要，再问第二个问题以区分线路 $2$ 和 $3$。如果答案是线路 $1$，只需问一次，否则需要问两次。因此，期望提问次数为 $(1 + 2 \times 2)/3$。 由 ChatGPT 4.1 翻译