Metro quiz#11747

Metro quiz

3 seconds

128 megabytes

Hard

Two spectators at the Olympic Games are waiting in a queue. Each of them has a copy of the Paris metro map, and they have invented a little game to pass the time. First, player $A$ thinks of one of the metro lines (choosing it uniformly at random among all lines), and player $B$ has to guess which line it is. To do this, player $B$ repeatedly asks whether the line stops at a station of his or her choice, and player $A$ truthfully answers each question. After a sufficient number of questions, player $B$ can usually determine for sure which line player $A$ had in mind. Of course, player $B$ wants to minimize the number of questions that need to be asked.

You are given a metro map describing $m$ lines (numbered from $1$ to $m$ ) and $n$ stations (numbered from $0$ to $n - 1$ n-1). For each line, the stations where the train stops are listed. Calculate the expected number of questions player $B$ needs to ask to determine the hidden line, using the optimal strategy.

In other words, let $S$ be some strategy, and let $Q_{S, j}$ Q_{S,j} denote the number of questions asked under strategy $S$ if the chosen line is $j$ . Then,

E_{S} = E [Q_{S}] = \frac{1}{m} j = 1 \sum m Q_{S, j}

E_S = E[Q_S] = \frac{1}{m} \sum_{j=1}^m Q_{S,j}

denotes the expected value of $Q_{S, j}$ Q_{S,j} when $j$ is chosen uniformly at random among all metro lines. Your task is to compute $min_{S} E_{S}$ \min_S E_S. If it is not always possible for player $B$ to determine the chosen line with certainty, print not possible.

Input

The first line contains an integer $n$ ( $1 \leq n \leq 18$ 1 \leq n \leq 18), the number of stations. The second line contains an integer $m$ ( $1 \leq m \leq 50$ 1 \leq m \leq 50), the number of lines. Then follow $m$ lines: the $k$ -th of these lines contains first a positive integer $p \leq n$ p \leq n, then a space, and then $p$ integers $s_{1}, s_{2}, \dots, s_{p}$ s_1, s_2, \ldots, s_p — the numbers of the stations where the train of line $k$ stops. Each line stops at any given station at most once.

Output

Print one number: the minimum expected number of questions that player $B$ must ask in order to determine the chosen line, or not possible (in lowercase). Answers within $1 0^{- 4}$ 10^{-4} of the correct answer will be accepted.

Examples

Explanation for sample 2. It is optimal to ask about station $0$ first, due to the symmetry of the task. This distinguishes line $1$ , which stops at station $0$ , from lines $2$ and $3$ , which do not. If necessary, a second question can distinguish between lines $2$ and $3$ .

Player $B$ asks one question if the chosen line is line $1$ , and two questions otherwise. Thus, the expected number of questions is $(1 + 2 \cdot 2) /3$ (1 + 2 \cdot 2)/3.

Example 1

Example 2