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

Два зрителя Олимпийских игр стоят в очереди. У каждого из них есть копия карты парижского метро, и они придумали небольшую игру, чтобы скоротать время. Сначала игрок $A$ загадывает одну из линий метро (выбирая её равновероятно среди всех линий), а игроку $B$ нужно её угадать. Чтобы угадать, игрок $B$ многократно спрашивает, останавливается ли линия на выбранной им станции, и игрок $A$ честно отвечает на каждый вопрос. После достаточного количества вопросов игрок $B$ обычно сможет с уверенностью определить, какую линию загадал игрок $A$. Разумеется, игрок $B$ хочет минимизировать количество вопросов, которые ему придётся задать.

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

Другими словами, пусть $S$ — некоторая стратегия, и $Q_{S,j}$ обозначает количество вопросов, заданных в рамках этой стратегии, если загаданной линией оказалась линия $j$. Тогда

обозначает математическое ожидание $Q_{S,j}$ при равномерном выборе $j$ из множества всех линий метро. Ваша задача — вычислить $mi{n}_S{E}_S$. Если для игрока $B$ не всегда возможно с уверенностью определить загаданную линию, выведите "not possible".

Giriş verilənləri

Первая строка содержит число $n(1\le n\le 18)$. Вторая строка содержит число $m(1\le m\le 50)$. Далее следуют $m$ строк: в $k$-й строке сначала записано положительное число $p\le n$, затем пробел и $p$ целых чисел $s_1,s_2,...,s_p$ — номера станций, на которых останавливается метро на линии $k$. Линия останавливается на каждой станции не более одного раза.

Çıxış verilənləri

Выведите одно число — минимальное ожидаемое количество вопросов, которые игроку $B$ нужно задать, чтобы угадать загаданную линию, или "not possible" (маленькими буквами). Ответы с точностью до $10^{-4}$ будут считаться верными.

Nümunələr

Пояснение к примеру 2. Сначала оптимально спросить о станции $0$ из-за симметрии задачи. Это позволяет отличить линию $1$, которая останавливается на станции $0$, от линий $2$ и $3$, которые на ней не останавливаются. Если нужно, задаётся второй вопрос, чтобы различить линии $2$ и $3$.

Игрок $B$ задаёт один вопрос, если загаданная линия — линия $1$, и два вопроса в противном случае. Таким образом, ожидаемое количество вопросов, которое он задаст, равно $(1+2\cdot 2)/3$.