Загадка про метро#11747

Загадка про метро

3 секунди

128 мегабайтів

Складна

Два глядачі Олімпійських ігор стоять у черзі. У кожного з них є копія карти паризького метро, і вони придумали невеличку гру, щоб скоротити час. Спочатку гравець $A$ задумує одну з ліній метро (випадково вибираючи одну з усіх ліній), а гравцю $B$ потрібно її вгадати. Для цього гравець $B$ багаторазово запитує, чи зупиняється лінія на вибраній станції, і гравець $A$ чесно відповідає на кожне питання. Після достатньої кількості питань зазвичай можна з упевненістю визначити, яку лінію задумав гравець $A$ . Звісно, гравець $B$ хоче мінімізувати кількість питань, які йому потрібно поставити.

Вам дано карту метро, яка описує $m$ ліній (пронумеровані від $1$ до $m$ ) і $n$ станцій (пронумеровані від $0$ до $n - 1$ n-1). Для кожної лінії вказані станції, на яких зупиняється потяг цієї лінії. Обчисліть математичне очікування кількості питань, які повинен задати гравець $B$ для визначення задуманої лінії, використовуючи оптимальну стратегію.

Інакше кажучи, нехай $S$ — деяка стратегія, а $Q_{S, j}$ Q_{S,j} — кількість питань, поставлених за стратегією $S$ , якщо задумана лінія $j$ . Тоді

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}

виражає математичне очікування $Q_{S, j}$ Q_{S,j} при випадковому виборі $j$ з-поміж усіх ліній метро. Ваше завдання — обчислити $min_{S} E_{S}$ \min_S E_S. Якщо гравець $B$ не завжди може з упевненістю визначити задуману лінію, виведіть not possible.

Вхідні дані

Перший рядок містить ціле число $n$ ( $1 \leq n \leq 18$ 1 \leq n \leq 18) — кількість станцій. Другий рядок містить ціле число $m$ ( $1 \leq m \leq 50$ 1 \leq m \leq 50) — кількість ліній. Далі йдуть $m$ рядків: $k$ -й з них містить спочатку додатне число $p \leq n$ p \leq n, потім пробіл і $p$ цілих чисел $s_{1}, s_{2}, \dots, s_{p}$ s_1, s_2, \ldots, s_p — номери станцій, на яких зупиняється лінія $k$ . Кожна лінія зупиняється на кожній станції не більше одного разу.

Вихідні дані

Виведіть одне число: мінімальне математичне очікування кількості питань, які гравець $B$ повинен поставити для визначення задуманої лінії, або not possible (малими літерами). Відповіді з точністю до $1 0^{- 4}$ 10^{-4} вважаються правильними.

Приклади

Пояснення до прикладу 2. Оптимально спершу запитати про станцію $0$ через симетрію задачі. Це дозволить відрізнити лінію $1$ , яка зупиняється на станції $0$ , від ліній $2$ та $3$ , які на ній не зупиняються. Якщо потрібно, друге питання дозволяє розрізнити лінії $2$ та $3$ .

Гравець $B$ ставить одне питання, якщо задумана лінія — лінія $1$ , і два питання в іншому випадку. Таким чином, математичне очікування кількості питань становить $(1 + 2 \cdot 2) /3$ (1 + 2 \cdot 2)/3.

Приклад 1

Приклад 2