Игра в Мафию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Финес и Ферб решили провести чемпионат по игре в Мафию в Денвилле.

В игре есть две роли — мирные жители и мафия (и тех, и тех может быть несколько). Роли игрокам раздаются в самом начале игры, после чего каждый игрок с ролью мирного жителя знает только свою роль, но не знает роли других игроков, в то время как каждый игрок с ролью мафии знает роли всех других игроков.

Далее играют несколько туров (ночей): каждой ночью некоторые пары игроков встречаются друг с другом. И в конце ночи объявляется одна жертва, которую убила мафия этой ночью. Каждую ночь мафия убивает ровно одного мирного жителя, и это делает ровно один из представителей мафии. Чтобы представитель мафии мог убить мирного жителя, между ними должна была произойти встреча.

Кендис следила за игрой, поэтому ей известно количество игроков, а также количество и описание всех ночей.

Помогите ей найти минимальное возможное количество представителей мафии в игре, при котором игра могла следовать известному ей сценарию, чтобы рассказать маме об опасной деятельности Финеса и Ферба.

Входные данные

В первой строке даны два целых числа $$$k$$$ и $$$m$$$ — количество игроков и количество ночей в игре ($$$2 \le k \le 200$$$, $$$1 \le m \le 200$$$, $$$1 \le k - m \le 15$$$).

Далее идет $$$m$$$ блоков — описание ночей. Описание $$$i$$$-й ночи начинается с $$$t$$$ блоков описания живых игроков ($$$t$$$ — количество игроков, живых на момент начала $$$i$$$-й ночи). Каждый блок состоит из двух строк:

Гарантируется, что все встречи были двусторонними. То есть, если игрок номер $$$a$$$ присутствует в списке встреч у игрока номер $$$b$$$, то и игрок $$$b$$$ присутствует в списке у игрока $$$a$$$.

В последней строке описания ночи дано целое число $$$v$$$ — номер игрока, который был убит этой ночью.

Гарантируется, что входные данные описывают корректную игру.

Выходные данные

Выведите одно целое число — минимальное количество игроков, которые должны играть за мафию, чтобы описанная игра могла произойти.

Пример

Входные данные
4 2
1 3
2 3 4
2 3
1 3 4
3 3
1 2 4
4 3
1 2 3
1
2 2
3 4
3 2
2 4
4 2
2 3
2
Выходные данные
1